518.零钱兑换 II

题目描述：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例1：

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例2：

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例3：

输入: amount = 10, coins = [10]
输出: 1

题解：本问题可以转化成一个完全背包问题，即当总金额为j时，使用前i个硬币可以达到的组合的最大数量。
即 $dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]](j > coins[i-1])$
具体代码如下：

class Solution {
    
    public int change(int amount, int[] coins) {
        /*
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        dp[0][0] = 1;
        for(int i=1;i<=n;i++)
        {
            dp[i][0] = 1;
            for(int j=1;j<=amount;j++)
            {
                if(j >= coins[i-1])
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                } 
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount];*/
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=coins[i-1];j<amount+1;j++)
            {

                dp[j] = dp[j] + dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
}

注释内的方法使用的是二维dp数组。但是考虑到在更新dp数组时，使用的是前一行的当前列和本行的前几列，因此在更新dp[i][j]时，dp[i][j-coins[i-1]]已经是最新的，而上一行的当前列可以直接获取。因此可以将dp数组压缩为1维数组。在更新当前行的dp[j]时，dp[j]中保存的是上一行的dp[j]，dp[j-coins[i-1]]也已经是当前行的数据。

除此之外，还需要记录一下背包问题的相关内容。
如果每一样物品仅有一件，对于本题而言则是每个数最多可取一次。那么对应的是01背包问题，其递推式是
$dp[i][j] = max{dp[i-1][j],dp[i-1][j-weight[i]]+value[i]}(j > weight[i])$
如果每样物品有 $n_i$ 件，则对应多重背包问题，其递推式是
$dp[i][j] = max{dp[i-1][j-k*weight[i]]+k*value[i]}(k = 0,1,···,n_i)$
如果每样物品有无穷多件，则对应完全背包问题，则其同一件可以取无数次，其递推式是
$dp[i][j] = max{dp[i-1][j],dp[i][j-weight[i]]+value[i]}(j > weight[i])$