算法训练营day37 | {1049.最后一块石头的重量 II, 494.目标和, 474.一和零}

第九章动态规划part04，01背包的应用题，不同的题目dp数组的含义一直在变化。

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

1.1 解题分析

问题转化：尽可能把石头分成重量相等的两堆，这样粉碎后剩余的重量就是最小的。每块石头的重量就是石头的价值，每块石头只能使用一次，问题转化为01背包问题。

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[j]的定义：从下标为[0~i]的物品任意取，容量为j的背包所背的最大价值。
  2. 确定递推公式: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  3. dp数组如何初始化: 容量为0时 dp[0]=0
  4. 确定遍历顺序: 只能先遍历物品，保持dp数组语义，并倒序遍历背包容量防止覆盖。
  5. 举例推导dp数组: stones = [2,7,4,1,8,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = Arrays.stream(stones).sum();
        int maxVol = total / 2;
        
        int target = knapsack(stones, maxVol);
        return total - target * 2;
    }

    private int knapsack(int[] stones, int w) {
        int[] dp = new int[w + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = w; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return dp[w];
    }
}

494. 目标和

2.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义: 取i个数，运算结果等于j的方式有dp[i][j]种
  2. 确定递推公式: num = nums[i - 1]是第i个数 dp[i][j] = dp[i - 1][j - num] + dp[i - 1][j + num]
  3. dp数组如何初始化: dp[0][0] = 1 ; dp[0][j != 0] = 0
  4. 确定遍历顺序: 先枚举用了几个数，再枚举所有可能的和。
  5. 举例推导dp数组: nums = [1,1,1,1,1], target = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int OFFSET = 2000;
    
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int total = Arrays.stream(nums).sum();
        if (total < Math.abs(target)) return 0;

        
        int[][] dp = new int[n + 1][OFFSET * 2 + 1];

        dp[0][OFFSET] = 1;

        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = -total; j <= total; j++) {
                dp[i][j + OFFSET] = dp[i - 1][j - num + OFFSET] + dp[i - 1][j + num + OFFSET];
            }
        }
        return dp[n][target + OFFSET];
    }
}

474. 一和零

3.1 解题分析

  • 因为背包既有个数0的限制(m)，也有个数1的限制(n)，字符串数组的个数(k)三个变量，需要用二维数组来定义。
  • 另外，第i个物品 0的个数设为x，1的个数设为y，作为物品重量。

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义: 0的个数为i、1的个数为j的背包最多能放下dp[i][j]个物品。
  2. 确定递推公式: dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j])
  3. dp数组如何初始化: dp[0][0] = 0; 其他位置为0
  4. 确定遍历顺序: 01背包问题都是先遍历物品，再倒序遍历背包。
  5. 举例推导dp数组:
  • 第一遍解题的时候，递推公式没写对，然后没有考虑背包容量是两个维度的时候，如果不省略物品这个维度，其实dp数组是三维的，遍历背包的容量仍然需要后序遍历，防止多次计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];

        for (int k = 0; k < len; k++) {
            int x = cntZero(strs[k]);
            int y = strs[k].length() - x;

            for (int i = m; i >=x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int cntZero(String str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') cnt++;
        }
        return cnt;
    }
}

4. 今日收获

  • 01背包的应用题挺难啊，有DP五部曲分析起来也比较困难，难点在于问题转化不好想，以及dp数组含义一直随题目目标在变动。
  • 学习时长：4小时