代码随想录算法训练营第四十三天| 1049 最后一块石头的重量 II 494 目标和 474 一和零
目录
1049 最后一块石头的重量 II
494 目标和
474 一和零
1049 最后一块石头的重量 II
class Solution {
public:const int N = 1505;int lastStoneWeightII(vector<int>& stones) {vector<int>dp(N);int sum = 0;for(int i = 0;i < stones.size();i++)sum += stones[i];int tar = sum / 2;for(int i = 0;i < stones.size();i++){for(int j = tar;j >= stones[i];j--){dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]);}}return sum - dp[tar] - dp[tar];}
};时间复杂度O(mn)m是石头的总重量的一半
空间复杂度O(m)
494 目标和
设sum为数组的总和
设加上部分的和为l，减去部分的和为r，则l - r = target，l = target + r，且l + r = sum，r = sum - l，l = target + sum - l，则l = (target + sum) / 2
由于target和sum都是确定的，所以本题只需要求出和为(target + sum) / 2的情况数
class Solution {
public:const int N = 1010;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((target + sum) % 2 == 1)return 0;int bagSiz = (target + sum) / 2;vector<int>dp(bagSiz + 1);dp[0] = 1;for(int i = 0;i < nums.size();i++){for(int j = bagSiz;j >= nums[i];j--){dp[j] += dp[j - nums[i]];}}return dp[bagSiz];}
};时间复杂度O(mn)m为背包大小，即(target + sum) / 2的值
空间复杂度O(m)
474 一和零
01背包问题
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m + 1,vector<int>(n + 1));for(string str : strs){int zeroSum = 0;int oneSum = 0;for(char ch : str){if(ch == '0')zeroSum++;else oneSum++;}for(int i = m;i >= zeroSum;i--){for(int j = n;j >= oneSum;j--){dp[i][j] = max(dp[i][j],dp[i - zeroSum][j - oneSum] + 1);}}}return dp[m][n];}
};时间复杂度O(mnl+L)l为字符串的总数，L为字符串中字符的总数
空间复杂度O(mn)