经典动态规划：完全背包问题

518. 零钱兑换 II

本篇文章介绍「完全背包」问题，但「0-1 背包」「子集背包」和今天介绍的「完全背包」是一个系列的问题！！

关于「0-1 背包」的详细介绍可见 经典动态规划：0-1 背包问题

关于「子集背包」的详细介绍可见 经典动态规划：子集背包问题

「完全背包」和其它两种背包唯一的区别就是：物品数量无限

问题分析

由于只有「物品数量」上的不同，所以其它地方几乎一样，只是dp的定义不同，以及状态转移不一样而已！！

明确「状态」和「选择」

状态：物品数量 & 背包容量

选择：是否装入物品

明确dp数组的定义

dp[i][j]定义如下：对于前i个物品，当前背包容量为j时，恰好装满的组合数量

我们也可以很快确定 base case。即：dp[...][0] = 1，因为背包容量为 0，无论物品数量是多少，均只有一种组合，什么也不装！

根据「选择」，思考状态转移的逻辑

dp[i][j] = 不把物品i装进背包的组合数 + 把物品i装进背包的组合数

如果不把物品i装进背包，显然组合数应该等于dp[i-1][j]，继承前i-1个物品的结果

如果把物品i装进背包，那么组合数应该等于dp[i][j - val[i-1]]

注意：这里是dp[i][j - val[i-1]]，而不是dp[i-1][j - val[i-1]]，因为物品数量是无限的，所以选择物品i装入背包后，还可以继续选择物品i装入背包

对于题目 零钱兑换 II，状态转移方程为：

代码实现

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length + 1][amount + 1];
    // base case
    for (int i = 0; i <= coins.length; i++) dp[i][0] = 1;
    for (int i = 1; i <= coins.length; i++) {
        for (int j = 1; j <= amount; j++) {
            // 装不下的情况
            if (j - coins[i - 1] < 0) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j];
        }
    }
    return dp[coins.length][amount];
}

空间优化

关于空间优化的技巧可见 动态规划之最长回文子序列「dp 空间优化」

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    // base case
    dp[0] = 1;
    for (int i = 1; i <= coins.length; i++) {
        for (int j = 1; j <= amount; j++) {
            // 装不下
            // if (j - coins[i - 1] < 0) dp[j] = dp[j];
            // else dp[j] = dp[j - coins[i - 1]] + dp[j];

            // 下面是合并写法
            if (j - coins[i - 1] >= 0) dp[j] = dp[j - coins[i - 1]] + dp[j];
        }
    }
    return dp[amount];
}