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

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

代码随想录链接

题目

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

给定表示一堆石头重量的正整数数组, 每次选出任意两块石头进行粉碎, 两块石头分别减去较小的石头的重量, 重复最后最多会剩下一块头, 求此时石头最小的可能重量.

题目分析

两两碰撞, 根据这一点可以将这个问题转化为将石头分成尽可能重量相同的两堆, 这种情况下两堆石头相撞之后剩下的石头重量最小. 问题也转化为了如何使用\(sum / 2\) 的背包装下更多的重量和价值在数值上相同的石头.

动态规划五部曲:

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

  \(dp[j]\)表示容量为\(j\)的背包, 最多可以装的价值为\(dp[j]\).

• 确定递归公式

  因为本题目中石头的重量和价值在数值上相同, 所以有\[dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]\].

• dp数组如何初始化

  dp数组的初始化要考虑两点, 一个是最大容量, 另一个是初始值

  在本题目中, 最大容量是所有石头的重量和, 也就是\(30 * 100 = 3000\).

  由于递推公式中包含了\(+ stone[i]\)这一部分, 所有初始值都可以初始化为0.

• 确定遍历顺序

  一维dp数组, 先遍历物品后遍历背包容量时, 外层正向循环, 内层背包容量倒序遍历.

• 举例推导

  举题目中的例子:

  输入 [2, 4, 1, 1], target = 8 / 2 = 4

  有dp数组:

  遍历	0	1	2	3	4
  用stone[0]遍历背包容量	0	0	2	2	2
  用stone[1]遍历背包容量	0	0	2	2	4
  用stone[2]遍历背包容量	0	1	2	3	4
  用stone[3]遍历背包容量	0	1	2	3	4

  确实是将石头分为[2, 1, 1] 和 [4] 之后, 最终的剩下的石头最小.

题解

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(1501, 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数组先物品后背包时, 背包容量逆向遍历
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        return sum - dp[target] - dp[target];   // dp[target]是分得的两堆石头中的较小的那个, 大的减去小的, 即可得到碰撞后最后一块石头的重量
    }
};

494.目标和

代码随想录链接

题目

LeetCode-494.目标和

给定一个非负整数数组和一个目标数, 向每个数前面添加'+'或'-'并串联起所有整数形成一个表达式, 求有多少个表达式之和为目标数.

题目分析

转化为0-1背包问题, 就可以将所有数字分为放+号的一个集合, 放-号的一个集合, 假设我们要求+号的集合, 设其为plus, 前面放-号的集合为minus, 有题目可知, plus + minus之和为sum, 而plus - minus的结果为目标数target, 消去minus, 可以得出plus = (sum + target) / 2.

此时问题就可以转化为装满plus容量的包, 有几种方法.(就是哪几个数来放+号)

动态规划五部曲:

• 确定dp数组及下标的含义

  \(dp[j]\)表示填满\(j\)容积的包, 有\(dp[j]\)种方法.

• 确定递推公式

  可以使用已经确定放入的物品, 以及不放这个物品的方法数来进行推测.

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

• dp数组的初始化

  填满容量为0的背包, 只有一种办法, 所以\(dp[0]\)应该初始化为1.

• 确定遍历顺序

  一维dp数组下, 外层循环物品, 内层循环容量, 且容量倒序循环.

• 举例推导

  nums:[1,1,1,1,1], target = 3

  遍历	0	1	2	3	4
  nums[0]遍历背包容量	1	1	0	0	0
  nums[1]遍历背包容量	1	2	1	0	0
  nums[2]遍历背包容量	1	3	3	1	0
  nums[3]遍历背包容量	1	4	6	4	1
  nums[4]遍历背包容量	1	5	10	10	5

题解

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 false;
        if ((target + sum) % 2)
            return false;
        int bagsize = (target + 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];
    }
};

474.一和零

代码随想录链接

题目

LeetCode-474.一和零

给定一个二进制字符串数组和两个整数m和n, 找出数组的最大子集的大小, 且该子集最多含有m个0和n个1.

题目分析

转化为0-1背包问题, 可以是每个字符串都视为一个物品, 一个物品有两个维度, 分别是0的个数和1的个数.

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i][j]: 最多有i个0和j个1的最大子集大小.

• 确定递推公式

  可以由前一个字符串推导出来.

  \[dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)\]

• dp数组的初始化

  初始化为0保证不会影响后续计算即可

• 遍历顺序

  外层循环物品, 内层逆向循环容量

• 举例推导

  懒了

题解

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 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];
    }
};