1、前言

题目描述

2、思路

本题使用完全背包的思路，那完全背包跟 0-1 背包有何区别呢？

0-1 限制了物品的数量，物品并不是无限的。假设有物品 weight 跟物品的价值 value，weight_i 表示每个物品的重量，value_i 表示每个物品对应的价值，在不超过背包容量的情况下怎样才能使得价值最大？其实对于每个物品来说，都可以放与不放。那么定义一个二位数组 dp[i][j] 表示在选择物品 i 、背包容量为 j 的情况下价值最大。

那么对于 dp[i][j] 来说，存在放第 i 个物品跟不放第 i 个物品。

在不放第 i 个物品的情况下，直接继承上一个背包的数据情况，即 dp[i][j] = dp[i - 1][j]。

在放第 i 个物品的情况下，那么需要加上第 i 个物品的价值 value_i[i - 1]（数组从 0开始），然后需要加上去掉 i 的重量的情况下，应该由哪个数据推导过来，即 dp[i - 1][j - weight_i[i - 1]]，所以 dp[i][j] = dp[i - 1][j - weight_i[i - 1]] + value_i[i - 1]。

所以最大价值为 dp[i][j] = max {dp[i - 1][j], dp[i - 1][j - weight_i[i - 1]] + value_i[i - 1]}

要牢牢记住一点，动态规划是自底向上，由已知推到未知。

那么对应完全背包来说，物品的数量是无限的，那么也存在上面放与不放的情况。
针对这题，针对物品 i，存在放0个，放1个，放 k 个，所以 dp[i][j] = dp[i - 1][j - 0 * coins[i]] + dp[i - 1][j - 1 * coins[i]] ....，而 dp[i][j - coins[i]] = dp[i][j - coins[i] - 0 * coins[i]] + dp[i][j - coins[i] - 1 * coins[i]] + ...。

那么，上面两式相减得：dp[i][j]−dp[i][j−coins[i]]=dp[i−1][j]，即 dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

3、代码

初始代码：

public class Solution {

    public int change(int amount, int[] coins) {
        int len = coins.length;
        if (len == 0) {
            if (amount == 0) {
                return 1;
            }
            return 0;
        }

        int[][] dp = new int[len][amount + 1];
        // 题解中有说明应该如何理解这个初始化
        dp[0][0] = 1;

        // 填第 1 行
        for (int i = coins[0]; i <= amount; i += coins[0]) {
            dp[0][i] = 1;
        }

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

优化后代码：

class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i < dp.length; i++) {
            // 没有 amount 时，不用凑数，直接得1
            // dp[0][i] 为 0，但是数组默认都是0，所以不用写
            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 - 1][j] + dp[i][j - coins[i - 1]];
                }
            }
        }

        return dp[coins.length][amount];
    }
}