算法D43 | 动态规划5 | 1049. 最后一块石头的重量 II 494. 目标和 474.一和零

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

本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。 

视频讲解：动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录

Python：

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total = sum(stones)target = total//2dp = [0] * (target+1)for stone in stones:for j in range(target, stone-1, -1):dp[j] = max(dp[j], dp[j-stone]+stone)return total - dp[target] - dp[target]

C++:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int total = 0;for (int i=0; i<stones.size(); i++) total += stones[i];int target = total/2;vector<int> dp(target+1, 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 total - dp[target] - dp[target];}
};

494. 目标和 

大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。  

视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和_哔哩哔哩_bilibili

代码随想录

Python:

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total = sum(nums)if (target + total)%2 == 1: return 0if (abs(target)>total): return 0bagSize = (target + total)//2dp = [0] * (bagSize+1)dp[0] = 1for num in nums:for j in range(bagSize, num-1, -1):dp[j] += dp[j-num]return dp[bagSize]

C++:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int total = 0;for (int i:nums) total+=i;if (abs(target) > total) return 0;if ((target+total)%2 == 1) return 0;int bagSize = (total+target)/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.一和零  

通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。

视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零_哔哩哔哩_bilibili

代码随想录

Python:

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0]*(n+1) for _ in range(m+1)]for s in strs:one_num = s.count('1')zero_num = len(s) - one_numfor i in range(m, zero_num-1, -1):for j in range(n, one_num-1, -1):dp[i][j] = max(dp[i][j], dp[i-zero_num][j-one_num]+1)return dp[m][n]

C++:

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 ch : str) {if (ch == '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];}
};