拼凑钱币

[编程题]拼凑钱币

热度指数：8900 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10000)

输出描述:

输出一个整数,表示不同的组合方案数

示例1

输入

输出

算法知识视频讲解

JavaScript

w布响丸辣

var n = parseInt(readline());
    var arr=[1,5,10,20,50,100];
    var dp = [];
    for(var i=0;i<n+1;i++){
        dp[i] = 1;
    }
    for(var i=1;i<arr.length;i++){
        for(var j=arr[i];j<=n;j++){
            dp[j] = dp[j] + dp[j-arr[i]];
        }
    }
    if(n==0)
        print(0)
    else 
        print(dp[n]);

发表于 2018-10-08 17:19:49 回复(0)