硬币划分
问题描述：
有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？
思路分析：
- 穷举法
int countWays(int n) {
int count = 1; // 全用1分的情况
for(int a1 = 0; a1 < n/10; a1++) {
int b1 = 10 * a1;
for(int a2 = 0; a2 <= n/5; a2++) {
int b2 = 5* a2;
for(int a3=0; a3<=n/2; a3++) {
count++;
}
}
}
return count;
}
- 动态规划
我们假设用m种纸币构成sum分：(sum = x_1*V_1 + x_2*V2 + ... + x_m*V_m)
(V_m)的系数的取值可分为 (lbrace0, 1, 2, ..., sum/V_m
brace) ：
[sum = x_1*V_1 + x_2*V2 + ... + (0|1|2|3...|K)*V_m
]
[K = sum/V_m
]
定义dp[i][sum] = 用前i种硬币构成sum的所有集合数
当 (x_m=0) 时，实际上就是前i-1种纸币组合sum，有dp[i-1][sum]种组合，所以：
[dp[i][sum] = dp[i-1][sum-0*V_m] + dp[i-1][sum-1*V_m] + ... + dp[i-1][sum-K*V_m]
]
[K = sum/V_m
]
对应的数学描述是：
[dp[i][sum] = sum_{k=0}^{sum/V_m} dp[i-1][sum-K*V_m]
]
如果我们用二位数组表示dp[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种纸币要组成sum：dp[0][sum] = 0。
int countWays(int n){
int money[] = {1, 2, 5, 10};
int dp[] = new int[n+1];
dp[0] = 0;
for(int i = 0; i < money.len; i++){
for(int j = 0; j <= n; j++){
dp[j] = dp[j] + dp[j - dp[i]];
}
}
return dp[n];
}