完全背包问题总结

每个物品是无限制的

也包括组合问题，排列问题：排列问题背包在外层遍历，组合问题物品在外层遍历。

  • 与01背包问题最大的不同是，因为一个物品可以装多次，==背包从前往后遍历==。
  • 组合问题不强调顺序，排列问题强调元素之间的顺序。

image-20220330110040999

组合问题

有多少种方法。

  • 递推公式： dp[j] = dp[j] + dp[j - nums[i]]
  • 初始化： dp[0] = 1
  • 外层遍历物品，内层遍历背包

遍历模板：

1
2
3
4
5
for(int i = 0; i < coins.length; i++){
    for (int j = coins[i]; j <= amount; j++){
        dp[j] = dp[j] + dp[j-coins[i]];
    }
}

518. 零钱兑换 II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++){
            // 相较于之前的组合问题，这里是最大的变化
            for (int j = coins[i]; j <= amount; j++){
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

322. 零钱兑换

  • 这个最重要的是要，跳过初始值。
  • 初始化：dp[0] = 0， 0的时候最少就是啥也不用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++){
            for (int j = coins[i]; j <= amount; j++){
                if (dp[j-coins[i]] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE? -1: dp[amount];
    }
}

排列问题

遍历模板：

  • 因为，存在顺序问题，所以要后遍历物品。
1
2
3
4
5
6
7
for (int i = 0; i <= target; i++){
    for (int j = 0; j < nums.length; j++){
        if (i >= nums[j]){
           // dp[i] = dp[i] + dp[i-nums[j]];
        }
    }
}

377. 组合总和 Ⅳ

  • 这是一道，组合与排列相结合的题目
  • 题目强调：顺序不同的序列被视作不同的组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++){
            for (int j = 0; j < nums.length; j++){
                if (i >= nums[j]){
                    dp[i] = dp[i] + dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 0; i <= n; i++){
            for (int j = 1; j <= 2; j++){
                if (i >= j){
                    dp[i] = dp[i] + dp[i-j];
                }
            }
        }
        return dp[n];
    }
}