1. 最后一块石头的重量

代码随想录：原文

力扣题目：1049.最后一块石头的重量II

1.1 思路

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

动规五步曲：

1. 确定dp数组以及下标的含义

• dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]
• 石头的重量是 stones[i]，石头的价值也是 stones[i]

2. 确定递推公式

• 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
• 本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

3. dp数组如何初始化

• 们要求的target其实只是最大重量的一半，所以dp数组开到最大重量的一半就行
• dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖

vector<int> dp(15001, 0);

4. 确定遍历顺序

• 物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历

for (int i = 0; i < stones.size(); i++) { // 遍历物品
    for (int j = target; j >= stones[i]; j--) { // 遍历背包
        dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}

5. 举例推导dp数组

• 最后dp[target]里是容量为target的背包所能背的最大重量。
• 在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的
• 那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

1.2 代码实现

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.size(); i++) { // 遍历物品
            for (int j = target; j >= stones[i]; j--) { // 遍历背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

2. 目标和

代码随想录：原文

力扣题目：494.目标和

2.1 思路

• 假设加法的总和为x，那么减法对应的总和就是sum - x
• 所以我们要求的是 x - (sum - x) = target，x = (target + sum) / 2
• 此时问题就转化为，装满容量为x的背包，有几种方法

如果(target + sum) / 2 不是整数或target的绝对值已经大于sum，其实就是无解的

动规五步曲：

1. 确定dp数组以及下标的含义

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

2. 确定递推公式

例如：dp[j]，j 为5：

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

3. dp数组如何初始化

• 初始化的时候dp[0] 要初始化为1，如果dp[0]是0的话，递推结果将都是0

4. 确定遍历顺序

• nums放在外循环，target在内循环，且内循环倒序（01背包）

5. 举例推导dp数组

2.2 代码实现

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

• 时间复杂度：$O(n × m)$，n为正数个数，m为背包容量
• 空间复杂度：$O(m)$，m为背包容量

3. 一和零

代码随想录：原文

力扣题目：474.一和零

3.1 思路

• 字符串的zeroNum和oneNum相当于物品的重量（weight[i]）
• 字符串本身的个数相当于物品的价值（value[i]）

动规五部曲：

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

2. 确定递推公式

• dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
• dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
• 然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

3. dp数组如何初始化

• 初始为0，保证递推的时候dp[i][j]不会被初始值覆盖

4. 确定遍历顺序

• 外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历

for (string str : strs) { // 遍历物品
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {
        if (c == '0') zeroNum++;
        else oneNum++;
    }
    for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
        for (int j = n; j >= oneNum; j--) {
            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}

5. 举例推导dp数组

3.2 代码实现

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};