问题描述
目前市面上的纸币主要有1元,5元,10元,20元,50元、100元六种,如果要买一件商品x元,有多少种货币组成方式?
解答
我们先进行如下变量的定义:
dp[i][sum] = 用前 i 种硬币构成sum金额的所有组合数。
那么题目的问题实际上就是求dp[m][sum],即用前m种硬币(所有硬币)构成sum的所有组合数。
V0=1,V1=5,V2=10,V3=20……
dp[i][sum] = dp[i-1][sum - 0*Vm] + dp[i-1][sum - 1*Vm]+ dp[i-1][sum - 2*Vm] + ... + dp[i-1][sum - K*Vm];
其中K = sum / Vm
换一种更抽象的数学描述就是:
我们可以这么考虑,希望用m
种纸币构成sum
元。
如果sum=0,那么无论有前多少种来组合0,只有一种可能,就是各个系数都等于0;
dp[i][0] = 1 // i = 0, 1, 2, … , m
如果我们用二位数组表示dp[i][sum], 我们发现第i行的值全部依赖与i-1行的值,所以我们可以逐行求解该数组。如果前0种纸币要组成sum,我们规定为dp[0][sum] = 0.
dp[j] 代表:之前 0 到 i-1 种货币组合成 j 元的种类数。
dp[j-money[i]] 代表:从 j 元中抽出一张money[i] 的货币(即加入了money[i]这种货币),剩下组合成j-money[i] 元的种类数。
由于dp[j]在不停地被替换,所以不用担心 dp[i-1][sum - 2*Vm] 这种,在算dp[j-money[i]] 的时候,那个时候这里面的种类数已经是最新最全的 包含了货币money[i]的了。
代码实现方式
public class Test {/*** @param x 商品金额*/public static void test(int n){//纸币面额int money[]={1,5,10,20,50,100};int dp[] = new int[n+1];dp[0] = 1;for(int i = 0;i < 6;++i){for(int j = money[i];j <= n;++j){dp[j] =(dp[j]+dp[j-money[i]]);}}System.out.println(dp[n]);}public static void main(String[] args) {//指定100元的金额test(100);}}
分析
这种思路属于算法中的动态规划。也是动态规划的经典题目。很明显,大大优化了性能问题。