[华为面试题]

1分2分5分的硬币三种，组合成1角，共有多少种组合
1*x + 2*y + 5*z=10
先用最简单的暴力求解

 private static int question1() {
        int count = 0;
        for (int i = 0; i <= 10; i++) {
            for (int j = 0; j <= 5; j++) {
                for (int k = 0; k <= 2; k++) {
                    if (i * 1 + j * 2 + k * 5 == 10) {
                        System.out.println(i + "+" + j + "+" + k);
                        count++;
                    }
                }
            }
        }
        return count;
    }

[创新工厂笔试题]

题意

有1分，5分，10分，25分四种硬币，每种硬币数量无限，给定n分钱，有多少组合可以组成n分钱
例如n=100，那么有一种可能的组合方式为 100 = 225+55+210+51

分析

因为给出的n直接牵涉到能够使用较大的面值 比如n = 15 它就不能够使用25的面值，只能从10 5 1这三种面值来组合。比如n = 25 我们可以使用0个25的面值而剩下的由10 5 1来进行组合， 10 可以由使用10 5 1来组合， 5可以由 5 1来组合，比如n=100，我们可以使用0个25，剩下的100交给 10 5 1去凑，也可以使用1个25，那么剩下的75也交给10 5 1去凑，也可以使用2个25，3个25，这样基本就是递归的思路了。因为涉及到两个变量在变化，我们可以在循环中使用递归来解决，其中递归的方法需要解决传入的变量的问题：涉及到钱的数量和对应面值的变化所以需要传入两个变化的量到方法中。
[思路1] 当然我们可以采用暴力枚举，各个系数可能的取值无非是x1 = {0, 1, ..., sum / V1}, x2 = {0, 1, ..., sum/ V2}等等。这对于硬币种类数较小的题目还是可以应付的，比如华为和创新工厂的题目，但是复杂度也很高O（sum/V1 sum/V2 sum/V3 * ...）

递推

 public static int countWays(int n) {
        if (n <= 0) return 0;
        int[] num = new int[]{1, 5, 10, 25};
        return countWayCore(n, num, num.length - 1);//从最大面值开始判断
    }

    public static int countWayCore(int n, int[] coins, int cur) {
        if (cur == 0) return 1;//出口 因为只有面值最小了
        int res = 0;
        //不选couns[cur]
        //要一个
        //要两个....
        for (int i = 0; i * coins[cur] <= n; i++) {//
            int shengyu = n - i * coins[cur];
            res += countWayCore(shengyu, coins, cur - 1);
        }
        return res;
    }

动态规划

　　再来看看递推(迭代)解法，迭代解法主要就是下一步要做的事由上一步通过某种关系来决定。比如这里种类数主要由两个变量来决定，所以需要二维数组来存储，分别是1~n，以及能够使用的哪些面值。每一个点存储的是种数。而递推解法的思路本质上是和递归一样的，只是表达的方式不一样而已。
解题思路：

给定一个数值sum，假设我们有m种不同类型的硬币{V1, V2, ..., Vm}，如果要组合成sum，那么我们有

sum = x1 V1 + x2 V2 + ... + xm * Vm 

求所有可能的组合数，就是求满足前面等值的系数{x1, x2, ..., xm}的所有可能个数。

[思路2] 从上面的分析中我们也可以这么考虑，我们希望用m种硬币构成sum，根据最后一个硬币Vm的系数的取值为无非有这么几种情况，xm分别取｛0, 1, 2, ..., sum/Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。

• sum = x1 V1 + x2 V2 + ... + 0 * Vm

• sum = x1 V1 + x2 V2 + ... + 1 * Vm

• sum = x1 V1 + x2 V2 + ... + 2 * Vm

• ...

• sum = x1 V1 + x2 V2 + ... + K * Vm  

　　其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：

• dp[i][sum] = 用前i种硬币构成sum 的所有组合数。

　　那么题目的问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum的所有组合数。在上面的联合等式中：当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！ xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp[i-1][sum -Vm]种; xn =2呢， dp[i-1][sum - 2 * Vm]种，等等。所有的这些情况加起来就是我们的dp[i][sum]。所以：

• dp[i][sum] = dp[i-1][sum - 0Vm] + dp[i-1][sum - 1Vm]

• +dp[i-1][sum - 2Vm] + ... + dp[i-1][sum - KVm]; 其中K = sum / Vm

换一种更抽象的数学描述就是：

　　通过此公式，我们可以看到问题被一步步缩小，那么初始情况是什么呢？如果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. 

打表 n=20

1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   
1   1   1   1   1   2   2   2   2   2   3   3   3   3   3   4   4   4   4   4   5   
1   1   1   1   1   2   2   2   2   2   4   4   4   4   4   6   6   6   6   6   9   
1   1   1   1   1   2   2   2   2   2   4   4   4   4   4   6   6   6   6   6   9   

递推解法1

    public static int countWays1(int n) {

        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[4][n + 1];//前i种面值,组合出面值j
        for (int i = 0; i < 4; i++) {
            dp[i][0] = 1;//凑出面值0,只有一种可能,第一列初始化为1
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 1;//用1来凑任何面值都只有一种凑法,第一行初始化为1
        }
        for (int i = 1; i <=3; i++) {//面值
            for (int j = 1; j <= n; j++) {//需求价值
                for (int k = 0; k * coins[i] <= j; k++) {//剩余面值
                    //求剩余
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
                }
            }
        }
        return dp[3][n];
    }

递推解法2

解法二 还是有点理解不了精髓，

    /*递推解法*/
    public static int countWays2(int n) {
        int[] coins = {1, 5, 10, 25};
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 0; i < 4; i++) {
            for (int j = coins[i]; j < n + 1; j++) {
                dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007;
            }
        }
        return dp[n];
    }

GitHub

参考文献

i>[1] 硬币问题