欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划-硬币组合数目

程序员文章站 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);
    }

}