[数据结构与算法]Java描述 LeetCode，518. Coin Change 2

题目描述：

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.


Example 1:

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
Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

Input: amount = 10, coins = [10]
Output: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2

idea

这个问题是完全背包的应用，不同之处，在于这边统计的是种类数，而不是最大的价值，和0-1背包的应用题 第494 target sum ，差不多的思想，只要用完全背包套路即可，这边给出完全背包的讲解视频，这个人讲的挺好的。
https://www.bilibili.com/video/BV1C7411K79w?p=2

dp四部曲

• dp状态：dp[i][j] 代表从前i个零钱中选择，使其总面值和为j，一共有dp[i][j]个种4方法
• 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - coin[i]];
• 初始化：dp[0][0] = 1 代表没有钱币可选，选出面值总和为0，一共有1种选择。
• 确定遍历顺序，通过状态方程可以看出依赖关系，从上到下，从左到右。

二维数组代码

    public static int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        // initialization
        dp[0][0] = 1;
        //row: 0~n  column: 0~amount
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < amount + 1; j++) {
                int coin = coins[i - 1];
                if (j >= coin) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coin];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));
        return dp[n][amount];
    }

滚动数组

    public static int change2(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];


        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

总结

完全背包问题还是得抓住几点

• 物品是可以无限放的
• 0-1背包是依赖于上一行，完全背包是依赖于同一行。
• 滚动数组，0-1从后向前遍历，完全背包从前向后，可以看上面的视频讲解了为什么。其实和值的覆盖有关系。