问题描述
目前市面上的纸币主要有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);}}
分析
这种思路属于算法中的动态规划。也是动态规划的经典题目。很明显，大大优化了性能问题。
