代码随想录算法训练营第四十三天| 1049. 最后一块石头的重量 II，494. 目标和，474.一和零

题目链接：1049. 最后一块石头的重量 II

思路

把石头分成重量尽量相同的两堆，这样就能保证最后一块石头的重量最小。转换为01背包问题，重量和价值都是stone。

①dp数组，dp[j]表示容量为j的背包可以装的最大价值为dp[j]

②递推公式，dp[j] = max(dp[j], dp[j - stone[i]] + stone[i])

③dp数组初始化，遍历stone数组，计算总重量，取一半为dp数组大小，值为0；或者根据题目可知最大重量为30*100=30000，取一半15000即可，值为0

④遍历顺序，一维dp数组，先物品，后背包，背包倒序遍历

⑤推导dp数组

代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.size() == 1)
            return stones[0];
        int sum = 0;
        // 计算总重量
        for (int a : stones)
            sum += a;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        // 先物品
        for (int i = 0; i < stones.size(); i++) {
            // 后背包
            for (int j = target; j >= stones[i]; j--) {
                // 01背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        // 分成两堆，一堆dp[target]，另一堆sum-dp[target]
        return sum - dp[target] - dp[target];
    }
};

题目链接：494. 目标和

思路

数组中有若干数字，在每个数字前面放加号或者减号使得最后的结果为target，可以理解为组合问题，使用回溯算法。每次遇到数字都是两种选择，如果最后等于目标，方法种类做累加操作。这种方法的问题在于时间复杂度，每次都是两种选择，并且数组中有若干数字，时间复杂度呈指数增长。

既然有加减两种运算符，那就将数组分为两个子集，加法子集left，减法子集right，数组所有数字之和为sum，则sum = left + right，target = left - right，联立两式可得left = (sum+target)/2，如此只需要在数组中寻找若干数字，使其和等于left即可，剩下的就是减法子集。将问题转化成了01背包问题。

①dp数组，dp[j]表示装满容量为j的背包有dp[j]种方法

②递推公式，dp[j] += dp[j-nums[i]]，举例，left=5时，装满需要dp[5]，而dp[5]可以由dp[4]+dp[1]得到，以此类推

③dp数组初始化，dp[0] = 1，因为要进行累加操作，所以dp[0]取1

④遍历顺序，先物品，后背包，背包倒序遍历

⑤推导dp数组

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 目标值的绝对值比数组中所有数字和还要大，肯定无解
        if (abs(target) > sum)
            return 0;
        // 不能整除，说明如何构造都满足不了题目要求
        if ((sum + target) % 2 == 1)
            return 0;
        int left = (sum + target) / 2; // 背包容量
        vector<int> dp(left + 1, 0);
        dp[0] = 1; // dp数组初始化
        // 先物品
        for (int i = 0; i < nums.size(); i++) {
            // 后背包，倒序遍历
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
};

题目链接：474.一和零

思路

01背包的思路，数组中由若干物品，重量有两个维度，0的个数，1的个数；背包的容量也有两个维度，0和1的容量，m和n，最后求的是背包最多可以装多少件物品。

重量及容量涉及两个维度，加上所求的物品数量，总共三个变量，所以使用二维dp数组。

①dp数组，dp[i][j]表示容量为i个0和j个0的背包最多可以装dp[i][j]件物品

②递推公式，dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1)，x表示当前物品0的个数，y表示当前物品1的个数

③dp数组初始化，dp[0][0]=0，容量都为0，装不了物品；dp数组中非0容量也初始化为0，这是因为在递推公式中涉及到max取最大值

④遍历顺序，先物品，后背包，背包倒序遍历

⑤推导dp数组

代码

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // dp数组及初始化
        // 01背包
        // 先物品
        for (string str : strs) {
            int x = 0; // 记录当前物品0的数量
            int y = 0; // 记录当前物品1的数量
            for (char a : str) {
                if (a == '0')
                    x++;
                else
                    y++;
            }
            // 后背包，这里有两个维度0和1，倒序遍历
            for (int i = m; i >= x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }
};