侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

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

thinkTV
2023-05-31 / 0 评论 / 0 点赞 / 103 阅读 / 1,585 字 / 正在检测是否收录...

1. 最后一块石头的重量

代码随想录:原文

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

1.1 思路

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

动规五步曲:

  1. 确定dp数组以及下标的含义
  • dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]
  • 石头的重量是 stones[i],石头的价值也是 stones[i]
  1. 确定递推公式
  • 01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  • 本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
  1. dp数组如何初始化
  • 们要求的target其实只是最大重量的一半,所以dp数组开到最大重量的一半就行
  • dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖
vector<int> dp(15001, 0);
  1. 确定遍历顺序
  • 物品遍历的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]);
    }
}
  1. 举例推导dp数组

图片-1

  • 最后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]种方法

  1. 确定递推公式

例如: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]]
  1. dp数组如何初始化
  • 初始化的时候dp[0] 要初始化为1,如果dp[0]是0的话,递推结果将都是0
  1. 确定遍历顺序
  • nums放在外循环,target在内循环,且内循环倒序(01背包)
  1. 举例推导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)O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(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]

  1. 确定递推公式
  • 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);

  1. dp数组如何初始化
  • 初始为0,保证递推的时候dp[i][j]不会被初始值覆盖
  1. 确定遍历顺序
  • 外层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);
        }
    }
}

  1. 举例推导dp数组

图片-5

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];
    }
};
0

评论区