【Day31 LeetCode】动态规划DP Ⅳ

一、动态规划DP Ⅳ

1、最后一块石头的重量II 1049

这题有点像脑筋急转弯，尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。明白这一点，就与上一篇博客里的划分等和数组很相似。划分等和数组是给定背包容量，能不能恰好填满该背包；这题是给定背包容量，尽可能填满该背包。直接套用代码。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int ss = accumulate(stones.begin(), stones.end(), 0);int s = ss / 2;vector<int> dp(s + 1);for(int stone : stones)for(int j=s; j>=stone; --j)dp[j] = max(dp[j], dp[j-stone] + stone);return ss - 2 * dp[s];}
};

2、目标和 49

这题需要变通一下，本质上是将原数组分成两个子集，记为left(表示+)和right(表示-)，两个子集需要满足： left = (target + sum)/2 。 left组合 - right组合 = target，left + right = sum，而sum是固定的，left - (sum - left) = target 推导出 left = (target + sum)/2 。与上一篇博客里的划分等和数组很相似。此时问题变成了 从nums数组中选取元素填满容量为left的背包的方法。这时套用01背包一维数组的代码，需要修改dp方程。对于二维数组，dp[i][j]表示在0~i中选取元素构成和为j的组合的个数，当前值dp[i][j]有选与不选物品i两个选择，所以递推方程为$dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]$，相应的一维为$dp[j]+=dp[j-nums[i]]$。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int s = accumulate(nums.begin(), nums.end(), 0);if(abs(target) > s || (target + s) % 2 == 1)return 0;s = (s + target) / 2;vector<int> dp(s + 1);dp[0] = 1;for(int i=0; i<nums.size(); ++i)for(int j=s; j>=nums[i]; --j)dp[j] += dp[j-nums[i]]; return dp[s];}
};

3、一和零 474

这题是给定背包容量，求装满背包最多有多少物品，并且该背包很特殊，有0和1的数量两个维度。套用优化掉物品维度的01背包代码，dp[i][j]表示最多有i个0和j个1的strs的最大子集的大小为dp[i][j]，这里采用二维数组表示背包的维度，物品的维度呗优化掉了，所以在遍历背包时需要和之前一样采用逆序遍历。

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 one = 0, zero = 0;for(char ss : str){if(ss=='1')++one;else++zero;}// 遍历背包for(int i=m; i>=zero; --i)for(int j=n; j>=one; --j)dp[i][j] = max(dp[i-zero][j-one] + 1, dp[i][j]);}return dp[m][n];}
};

二、写在后面

难点在于将问题分析清楚，理清如何转换成背包问题。第一题是给定背包容量，尽可能装，最多能装多少；第二题是给定背包容量，求装满背包的方法；第三题是给定背包容量，求装满背包最多有多少物品，并且此背包比较特殊，有两个维度。