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

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

（脑子没转过弯x1）

初见半天没想明白，背包问题一次不是只取一个物品吗，这题怎么一次取两个呀？？？

其实这题的思路能够转换成 416分割等和子集：

思路有了，代码其实和416差不多，只有最后的返回值部分有些差别

int lastStoneWeightII(vector<int>& stones) {
	int sum = 0;
	for (int n : stones)
		sum += n;
	// 取总重量的一半作为目标值
	// 由于 /2 省略了小数，所以target必定小于等于sum的一半
	int target = sum / 2;

	vector<int> dp(target + 1, 0);
	for (int i = stones[0]; i <= target; ++i)
		dp[i] = stones[0];

	for (int i = 1; i < stones.size(); ++i) {
		for (int j = target; j >= stones[i]; --j) {
			dp[j] = std::max(dp[j], dp[j - stones[i]] + stones[i]);
		}
	}
	// sum - dp[target]是稍重一组的重量，dp[target]是稍轻一组的重量
	return (sum - dp[target]) - dp[target];
}

---

494.目标和

（脑子没转过弯x2）

初见也是没想明白，这次是只取一个物品了，但物品怎么能又加又减两种操作呀？？？

其实通过数学分析，能将两种操作变为一种：

动规五部曲：

int findTargetSumWays(vector<int>& nums, int target) {
	int sum = 0;
	for (int n : nums)
		sum += n;

	int newTarget = sum + target;
	// 除2除不尽说明没有解，target的绝对值大于sum也没有解，直接返回0
	if (newTarget % 2 == 1 || std::abs(target) > sum)
		return 0;
	else
		newTarget /= 2;

	// dp[i] 表示和为i的子集数量
	vector<int> dp(newTarget + 1, 0);
	dp[0] = 1;

	for (int i = 0; i < nums.size(); ++i) {
		for (int j = newTarget; j >= nums[i]; --j) {
			// 不加nums[i]：dp[j]保持不变
			// 加nums[i]：dp[j] += dp[j - nums[i]]
			dp[j] += dp[j - nums[i]];
		}
	}
	return dp[newTarget];
}

---

 474.一和零

 这题重点在理解题意，题目中每个元素只使用一次，但对背包有m和n两个限制，所以这题是一个背包有两个维度的0-1背包问题

int findMaxForm(vector<string>& strs, int m, int n) {
	vector<vector<int>> nums;
	for (string s : strs) {
		vector<int> vec(2, 0);
		for (char c : s)
			++vec[c - '0'];
		nums.push_back(vec);
	}

	// 两个维度的背包
	// dp[i][j]表示 m = i，n = j 时最长的子集长度
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

	for (int k = 0; k < nums.size(); ++k) {
		for (int i = m; i >= nums[k][0]; --i) {
			for (int j = n; j >= nums[k][1]; --j) {
				// 不将当前元素加入子集：长度 = dp[i][j]
				// 将当前元素加入子集：长度 = dp[i - nums[k][0]][j - nums[k][1]] + 1
				dp[i][j] = std::max(dp[i][j], dp[i - nums[k][0]][j - nums[k][1]] + 1);
			}
		}
	}
	return dp[m][n];
}

---

总结

对于要分为两组的问题，需要进行一定的数学推理将其变为一组，如：

        1049：将石头分为重量尽可能接近的两组 -> 分出一个子集，其总和尽可能接近总重量的一半

        494：将所有元素分为+的一组和-的一组，经过数学推理 -> 求统计总和为 (sum + target) / 2 的子集数量