LeetCode -- Dynamic Programming例

今天在leetcode上做了几道dynamic programming的题。就其中两道题做个总结吧。

• coin change （Part 1)
• coin change 2 (Part 2)

Part 1部分介绍了coin change这题的解法，是个非常典型的dynamic programming问题。接下来，看看coin change 2。
这题的问题是给了一些硬币的面值和一个数值，要求返回要由这些面值的硬币组成这个数值，一共由多少中组成方法。
下面是一个例子：
···
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
···
当看到这题的第一反应是想到了跳楼梯那个问题（一次可以跳一步或者两步，要求跳到第n个台阶有几种方法）。也就是得出了这个算式。但是其实跳楼梯问题和本题有着一个很大的不同点：在楼梯问题中是有顺序的，也就是说，1 1 2 和1 2 1是两种方法，但是在硬币组成的问题中，这两个是同一种组成方式，都是由两个1元硬币和一个2元硬币组成，因此不能用这种方法。

这题和前面的那题不一样，不需要把从上到下转化为从下到上变成一个dynamic programming，而是正向地从下到上地思考。

借助下面这个表格来解释解法：

这个表格的列标题需要组成的数字amount(0-6)，行标题表示硬币的种类，每一行增加一种硬币，每一行中的数字表示由这些硬币所能组成的方式有多少种。
初始化第一行，0能够由空组成，所以是1，而别的数字都是0.
接下来是这些数字的计算过程。
[1]1这里的0+1表示的是不加入新的硬币1，能够由多少组成方式0([]1), 如果加入1这种硬币，组成方式就会变成amount-coin这个值所拥有的组成方式。所以更新后的数值为这两者的和
代码如下：

public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= coins.length; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
            }
        }
        return dp[coins.length][amount];
    }

由于dp[i][j]= dp[i-1][j] + dp[i][j-coins[i]]
可以进行一定的简化：

public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }

总结：分层次。