笔试题：硬币划分

硬币划分

问题描述：

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

思路分析：

1. 穷举法

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;
}

1. 动态规划

我们假设用m种纸币构成sum分：$sum = x_1V_1 + x_2V2 + ... + x_m*V_m$
$V_m$的系数的取值可分为 $\lbrace0, 1, 2, ..., sum/V_m\rbrace$ ：

$$ 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-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];
}