动态规划-硬币组合数目
程序员文章站
2024-03-26 10:10:17
...
import java.util.Scanner;
/*
* 硬币的类型有1角,2角,5角,给定一个数额n,多少种组合方式
*/
//暴力解法
public class CashNum {
public int getNum(int n){
int count=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j=j+2)
for(int k=0;k<=n;k=k+5)
if(i+j+k==n){
//System.out.println(n+"="+i+"+"+j+"+"+k+" ");
count++;
}
return count;
}
public int getNum2(int[] array,int n){
if(array.length==0||array==null||n<0)
return 0;
int[][] dp=new int[array.length+1][n+1];
for(int i=0;i<array.length+1;i++)
for(int j=0;j<n+1;j++)
dp[i][j]=0;
for(int i=0;i<array.length+1;i++)
dp[i][0]=1;
for(int i=1;i<array.length+1;i++)
for(int j=1;j<n+1;j++){
dp[i][j]=0;
for(int k=0;k<=j/array[i-1];k++){
dp[i][j]+=dp[i-1][j-k*array[i-1]];
}
}
return dp[array.length][n];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CashNum cn=new CashNum();
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
int count=cn.getNum(n);
int[] array={1,2,5};
System.out.println("count="+count);
int count2=cn.getNum2(array, n);
System.out.println("count2="+count2);
}
}