java动态规划硬币划分,笔试题：硬币划分 - osc_8iux0cyz的个人空间 - OSCHINA - 中文开源技术交流社区...

硬币划分

问题描述：

有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_1V_1 + x_2V2 + ... + x_m*V_m$ $V_m$的系数的取值可分为 $lbrace0, 1, 2, ..., sum/V_mrbrace$ ：

$$ sum = x_1V_1 + x_2V2 + ... + (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-0V_m] + dp[i-1][sum-1V_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];

}