2026.03.21 03.09 第四十一天
1049 最后一块石头的重量||
和上一题的思想一样
关键是想到把问题转化为把石头尽可能分成重量近似，数量相同的两堆，然后求重量差。
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int weightSum = 0;int weight = 0;for(int& i : stones) weightSum += i;weight = weightSum / 2;vector<int> dp(weight + 1, 0);for(int i = 0; i < stones.size(); i++) {for(int j = weight; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return abs(weightSum - 2 * dp[dp.size() - 1]);}
};
494 目标和
相比上一题难度更甚，需要重新推导递推公式。
首先需要想明白目标和怎样转化成01背包问题，也就是如下思路：
本题要如何使表达式结果为target，
既然为target，那么就一定有 left组合 - right组合 = target。
left + right = sum，而sum是固定的。right = sum - left
left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
进而利用递推公式和01背包套路解决问题。
一维数组内层循环中的判断调节保证了数组不会越界，没有更改的数值本来应该更改为上一层i的值，然而因为是原地操作，本身存储的数字就是上一层的数字，所以不用更改。
本题要如何使表达式结果为target，既然为target，那么就一定有 left组合 - right组合 = target。left + right = sum，而sum是固定的。right = sum - leftleft - (sum - left) = target 推导出 left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。此时问题就是在集合nums中找出和为left的组合。
474 一和零
代码很简短，过程很心酸~
这个的背包从原来的一维变成了两个维度，因此代码结构发生了很大变化，原地操作也需要上二维的dp数组。
并且对每个字符串进行处理时（相当于遍历原来的每个物品时），需要先统计每个字符串（物品）的特性也就是0和1的数量，而后使用递推式，从后向前处理，
画一遍dp矩阵的变化就明白处理过程了。
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;int 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];}
};