这是我的人生处女面遇到的一个面试题，是在去哪儿网二面遇到的，那时非常的紧张，还没有复习，所以第一次面试理所应当的挂了。文章对问题进行逐步的由简到难进行优化，基本上是代码，看懂代码才能理解，也为类似问题提供了基本的解决思路。

题目描述：

让你把一张整钱找零，即假设你拥有不同且不限量的小额钱币，你需要统计共有多少种方法可以用手中的小额钱币兑等额兑换一张大额钱币。

即：给定一个元素为正数的集合（元素不重复）代表不同面值的钱币，再给一个整数，代表要找零的钱数，求共有多少种换钱方法？

递归求解

现在有1、5、10元三种面值的纸币，需要找零100元，那么可以做如下分析：

用 0 张 5 元换，剩下的用 1、10 元换，最终方法数为 count0；
用 1 张 5 元换，剩下的用 1、10 元换，最终方法数为 count1；
......
用 100 张 5 元换，剩下的用 1、10 元换，最终方法数为 count100；

最终的换钱方法总数就为 count0 + count1 + ...... + count100。

根据上面的分析可以写出下面的递归解决方案：

public static int coin(int money[], int target){
    if (money == null || money.length == 0 || target < 0){
        return 0;
    }else {
        return slove(money, 0, target);
    }
}

// 用money[index, length-1]换钱，返回总的方法数
private static int slove(int money[], int index, int target){
    int res = 0;
    if(index == money.length){
        if (target == 0){
            res = 1;
        }else {
            res = 0;
        }
    }else {
        for (int i = 0; money[index] * i <= target; i++) {
            res += slove(money, index+1, target-money[index]*i);
        }
    }
    return res;
}

优化递归

可以看到，上面的程序在运行时存在大量的重复过程，比如下面两种情况，其后所求结果是一样的。

兑换 100 元，已经使用了 0 张 1 元、1 张 2 元，剩下的用 5 元和 10 元兑换；
兑换 100 元，已经使用了 2 张 1 元、0 张 2 元，剩下的用 5 元和 10 元兑换；

可以发现，这两种情况后面都是求解同一问题，重复的对同一个问题求解，就造成了时间的浪费，因此我们可以考虑将已经计算过的结果存下来，避免重复的计算，所以有下面的优化方案。

public static int coin(int money[], int target){
    if (money == null || money.length == 0 || target < 0){
        return 0;
    }else {
        /**
         * map[i][j]表示p(i,j)递归回的值
         * 其中-1表示该递归过程计算过，但是返回值为0
         * 0表示该递归过程还为计算过
         */

        int map[][] = new int[money.length+1][target+1];
        return slove(money, 0, target, map);
    }
}

private static int slove(int money[], int index, int target, int map[][]){
    int res = 0;
    if(index == money.length){
        if (target == 0){
            res = 1;
        }else {
            res = 0;
        }
    }else {
        int val = 0;
        for (int i = 0; money[index] * i <= target; i++) {
            val = map[index + 1][target - money[index]*i];
            if (val != 0){
                if (val == -1){
                    res += 0;
                }else {
                    res += val;
                }
            }else {
                res += slove(money, index+1, target-money[index]*i, map);
            }
        }
    }

    if (res == 0){
        map[index][target] = -1;
    }else {
        map[index][target] = res;
    }
    return res;
}

动态规划

上面对递归方法的优化已经能看到动态规划的影子了，这是一个二维的动态规划问题，我们定义dp[i][j]的含义为：使用money[0...i]的钱币组成钱数j的方法数。所以可以得出以下面的动态规划解法：

public static int coin(int money[], int target){
    if (money == null || money.length == 0 || target < 0){
        return 0;
    }

    int dp[][] = new int[money.length][target+1];

    // 第一列表示组成钱数为0的方法数，所以为1
    for (int i = 0; i < money.length; i++) {
        dp[i][0] = 1;
    }
    // 第一行表示只使用money[0]一种钱币兑换钱数为i的方法数
    // 所以是money[0]的倍数的位置为1，否则为0
    for (int i = 1; money[0] * i <= target; i++) {
        dp[0][money[0] * i] = 1;
    }

    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            for (int k = 0; j >= money[i] * k; k++) {
                // dp[i][j]的值即为，用money[0...i-1]的钱
                // 组成j减去money[i]的倍数的方法数
                dp[i][j] += dp[i-1][j-money[i]*k];
            }
        }
    }

    return dp[money.length-1][target];
}

继续优化

可以发现上面的动态规划解法有三层循环，因为是二维的动态规划问题，前两层没办法去掉，但是第三层依旧很耗时间，继续优化可以得到下面的结果。

public static int coin(int money[], int target){
    if (money == null || money.length == 0 || target < 0){
        return 0;
    }

    int dp[][] = new int[money.length][target+1];

    for (int i = 0; i < money.length; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; money[0] * i <= target; i++) {
        dp[0][money[0] * i] = 1;
    }

    for (int i = 1; i < money.length; i++) {
        for (int j = 1; j <= target; j++) {
            /**
             * 通过分析可以发现，dp[i][j]的值由两部分组成
             * 1：用money[0...i-1]的钱组成钱数为j的方法数
             * 2：用money[0...i]的钱组成钱数为j-money[i]*k（k=1,2,3....）的方法数
             * 对于第2种情况，实际上累加的值就是dp[i][j-money[i]]
             * 所以直接使用dp[i][j-money[i]]即可
             */
            dp[i][j] = dp[i-1][j];
            if (j >= money[i]){
                dp[i][j] += dp[i][j-money[i]];
            }
        }
    }

    return dp[money.length-1][target];
}

空间压缩

可以看到每次更新dp[i][j]，dp[i][j]的值只与前一行和当前行前面的元素有关系，而我们只需要最后的一个结果就行了，那么前面存的元素实际上会造成空间的浪费，进一步可以在空间上进行优化。

我们只需要定义一个一位数组，然后对该数组进行滚动更新就可以了，只要按照合适方向去更新数组，同样能达到上面的效果。

public static int coin(int money[], int target){
    if (money == null || money.length == 0 || target < 0){
        return 0;
    }

    int dp[] = new int[target+1];

    // 第一行，只用money[0]兑换钱
    // 所以只能兑换为money[0]的倍数，将这些位置置为1
    for (int i = 0; money[0]*i <= target; i++) {
        dp[i] = 1;
    }

    for (int i = 1; i < money.length; i++) {
        for (int j = 1; j <= target; j++) {

            // 与前一步相比，少了dp[i][j] = dp[i-1][j];
            // 因为这里在进行dp[j] += dp[j-money[i]];之前
            // dp[j]的值就已经是dp[i-1][j]了
            if (j >= money[i]){
                dp[j] += dp[j-money[i]];
            }
        }
    }

    return dp[target];
}

到这一步就不再有优化空间了，这个问题很值得记录下来，很多笔试、面试题都可以按这个模子进行套，对于只需要最优解的动态规划问题也可以套用上面的空间压缩思路，多总结、多练习总是没有问题的！这个解题思路第一次看到是左程云在牛客网上讲解的，他也写了一本算法相关的书比较不错，叫做程序员代码面试指南，大四、研三、刚入职的新人建议可以买一本读读，对自己编码技能的提升绝对又很大的帮助。