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

发布于 2023-02-28  290 次阅读


AI 摘要

Excerpt: For problem 1049, we can solve it using dynamic programming by dividing the stone weights into two piles with weights as close as possible and computing the difference between the two piles. We define dp[j] to be the maximum weight that can be accommodated when the weight of the pile is j. To calculate dp[j], we use the recurrence equation dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]). For problem 494, we can transform the problem into a knapsack problem where the target sum is the capacity of the knapsack and the positive and negative numbers are the items to be packed. We define dp[j] as the number of ways to fill a knapsack with capacity j. We can use the recurrence equation dp[j] += dp[j-nums[i]] to calculate the number of ways to reach the target sum.

1049. 最后一块石头的重量 II - 力扣(Leetcode)

思路:

  • 这道题和416. 分割等和子集 - 力扣(Leetcode)很相似,只需要把石头的重量分成重量最接近的两堆,然后取差值即可

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

      • dp[j]的定义为:重量为j时能装的最大石头重量
    2. 确定递推公式

      • 状态转移方程为dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    3. dp数组如何初始化

      vector<int> dp(1501, 0);
    4. 确定遍历顺序

      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[target]代表的是分成两堆后重量较小的那一堆石头的重量

我的AC代码

// 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
// 空间复杂度:O(m)
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i = 0; i < stones.size(); ++i) {
            sum += stones[i];
        }
        int target = sum / 2;
        vector<int> dp(1501, 0);
        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 - 2 * dp[target];
    }
};

标准答案

// 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
// 空间复杂度:O(m)
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];
    }
};

494. 目标和 - 力扣(Leetcode)

思路:

  • 这道题求的是是否能达成目标值target,那么一定有

    • left - right = target

    • left + right = sum

    • right = sum - left

    • left - (sum - left) = target

    • 所以left = (sum + target) / 2

  • 那么该题目就转化成当背包容量为left时有几种装满背包的办法

  • 我们先排除不可能填满的情况,然后再讨论动态规划的处理办法

      1. target绝对值大于sum
      2. (sum + target) / 2不是偶数
  • 以下为动态规划处理办法

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

      • dp[j]的定义为:填满容量为j的背包的方法数
    2. 确定递推公式

      • 因为求的是组合问题,所以状态转移方程为dp[j] += dp[j - nums[i]]; ,相当于遍历每一个新物品时都要将前面的最大值加上
    3. dp数组如何初始化

      dp[0] = 1;
    4. 确定遍历顺序

      for(int i = 0; i < nums.size(); ++i) {
          for(int j = left + 1000; j >= nums[i] + 1000; --j) {
              dp[j] += dp[j - nums[i]];
          }
      }

我的AC代码

原代码

// 时间复杂度O(m x n),空间复杂度O(n)
// m 代表 (target + sum) / 2
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(target > sum || ((target + sum) % 2 == 1)) {
            return 0;
        }
        int left = (target + sum) / 2;
        vector<int> dp(11000, 0);
        dp[1000] = 1;
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = left + 1000; j >= nums[i] + 1000; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left + 1000];
    }
};

进一步减枝代码

target绝对值大于sum的直接去掉

// 时间复杂度O(m x n),空间复杂度O(n)
// m 代表 (target + sum) / 2,即背包容量
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(target > sum || ((target + sum) % 2 == 1)) {
            return 0;
        }
        int left = (target + sum) / 2;
        vector<int> dp(11000, 0);
        dp[1000] = 1;
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = left + 1000; j >= nums[i] + 1000; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left + 1000];
    }
};

标准答案

// 时间复杂度O(m x n),空间复杂度O(n)
// m 代表 (target + sum) / 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];
    }
};

474. 一和零 - 力扣(Leetcode)

思路:

  • 这道题是01背包的变式,和普通01背包不同的是这道题的“重量”有两个维度,分别是单个字符串中0的数量和1的数量,所以应该建立一个二维数组

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

      • dp[i][j]的定义为:背包中最多能容纳i个0和j个1时的最大子集数
    2. 确定递推公式

      • 状态转移方程为dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
    3. dp数组如何初始化

      vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    4. 确定遍历顺序

      • 先遍历每个字符串,同时统计该字符串中0和1的数量
      • 然后倒序遍历dp数组

我的AC代码

// 时间复杂度O(m x n x k),空间复杂度O(m x n)
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int k = 0; k < strs.size(); ++k) {
            int zeroNum = 0;
            int oneNum = 0;
            for(char c : strs[k]) {
                if(c == '1') {
                    oneNum++;
                }
                else {
                    zeroNum++;
                }
            }
            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];
    }
};

标准答案

// 时间复杂度O(m x n x k),空间复杂度O(m x n)
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];
    }
};