Java中的硬币找零问题及解决方案

• Z时代
• 2024-01-10
• 分类：综合

问题：

您正在一个游乐场上的收银台工作，并且有无限数量的不同类型的硬币可供您使用。每个硬币的值已经给出。您能确定使用给定类型的硬币对特定数量单位进行更改的方式数量吗？

示例

如果您有3种硬币，并且每种硬币的值分别为1,2,3，则可以用以下四种方法更改4个单位：

    {1,1,1,1}  
    {1,1,2}     
    {1,3}       
    {2,2}       
    Distribute as total sum is 4.
    f(4)=1+f(3)
    f(4)=2+f(2)
    f(4)=3+f(1)      
    f(3)=1+f(2) and so on

解决方案代码（java代码）：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
	static long[][]  memo;
	static long count(int i,long coin[],int j){
		if(i==0)
			return 1;
		if(i<0)
			return 0;
		if(j<=0) 
			return 0;
		if(memo[i][j]!=-1) 
			return memo[i][j];
		memo[i][j]=count(i,coin,j-1)+count(i-(int)coin[j-1],coin,j);  
		// memo [i] [j] = memo [i] [j-1] + memo [i-value（c [j-1]）] [j] 
		//where  0<=j<=m hence j-1 is used.
		//例如，如果c [] = 1,2,3和n = 4，则 
		// memo [4] [3] = memo [4] [2] + memo [4- value（c [2]]）] [3]
		// ie memo [4] [3] = memo [4] [2] + memo [1] [3]
		return memo[i][j];
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		long c[]=new long[m];
		memo=new long[n+1][m+1];
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++) 
				memo[i][j]=-1;
		for(int c_i=0; c_i < m; c_i++){
			c[c_i] = in.nextLong();
		}
		long ways=count(n,c,m);
		//打印更改'n'的方法数量 
		//使用具有'c'给定值的硬币的单位
		System.out.println(ways);
	}
}

输出结果

以上是 Java中的硬币找零问题及解决方案 的全部内容， 来源链接： utcz.com/z/316045.html