leetcode hot100零钱兑换Ⅱ

本题可以看出也是背包问题，但区别于之前的01背包问题，这个是完全背包问题的变形形式。

下面介绍01背包和完全背包的区别与联系：

1. 01背包是背包中的物品只能用一次，不可以重复使用，而完全背包则是可以重复使用。
2. 01/完全背包的递推公式（这里都是以一维数组的情况举例）是dp[j] = Math.max(dp[j]，dp[j-weight[i]]+values[i])。
3. 01背包的遍历顺序是先物品，再背包，并且背包遍历的时候是需要倒序遍历的，而完全背包则不需要，直接先物品再背包（背包需要正序），其实先背包再物品也可以，但为了方便记忆则和01保持一致。

而当在完全背包的变形形式，比如本题是要求组合数，组合是没有顺序的，只需要找出对应的元素就可以，所以递推公式是dp[j] += dp[j-nums[i]]。

所以本题中，我们可以想将背包中的硬币个数，不限制次数的选取，最后求凑成金额为amount的种类一共有多少种。

所以采用动态规划完全背包求组合情况

dp[j]表示背包容量为j的价值为dp[j]。
dp[j] += dp[j-nums[i]]
dp[0] = 1 （注意，这里必须是1，如果不是1的话没办法推出后面的数据，后面数据就都变成0了）。
遍历顺序应该先物品再背包，并且背包内层循环应该由小到大遍历。
打印

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。