01背包问题总结

每个物品只能用一次

包括组合问题，排列问题。

遍历顺序模板

一般的dp数组定义是：

  • 容量为j的背包的可以凑成的子集的总和
  • 容量为j的背包的可以凑成的目标和的个数

一般是先遍历物品，再遍历背包，而且因为每个物品只能放入一次，所以背包从后向前遍历

1
2
3
4
5
6
for (int i = 0; i < stones.length; i++){
    for (int j = bagsize; j >= stones[i]; j--){
       // dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
       // 状态转移公式
    }
}

普通01背包问题

状态转移公式一般为： dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])

416. 分割等和子集

  • dp数组含义是，在容量为i的背包中，能装下的最多东西是dp[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if (sum % 2 == 1) return false;
        int bagsize = sum / 2;
        int[] dp = new int[bagsize+1];
        for (int i = 0; i < nums.length; i++){
            for (int j = bagsize; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+ nums[i]);
                if (dp[j] == bagsize){
                    return true;
                }
            }
        }
        return false;
    }
}

1049. 最后一块石头的重量 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) sum += stones[i];
        int bagsize = sum / 2;
        int[] dp = new int[bagsize + 1];
        for (int i = 0; i < stones.length; i++){
            for (int j = bagsize; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }
        return Math.abs(sum - 2 * dp[bagsize]);
    }
}

01背包组合问题

就是有多少种情况的。

状态转移公式一般为： dp[j] = dp[j] + dp[j-nums[i]]

494. 目标和

  • dp含义： 在背包容量是i的背包中，填满i有dp[i]种方法。
  • 初始化：dp[0] = 1，填满0的背包只有一种方法，什么也不装。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        target = Math.abs(target);
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if ((sum + target) % 2 == 1) return 0;

        int bagsize = (sum + target) / 2;
        int[] dp = new int[bagsize + 1];
        dp[0] = 1; 
        for (int i = 0; i < nums.length; i++){
            for (int j = bagsize; j >= nums[i]; j--){
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        return dp[bagsize];
    }
}