jsp企业网站,有哪个网站做策划方案的,免费个人简历电子版填写,wordpress 工单一、动态规划DP Ⅳ
1、最后一块石头的重量II 1049
这题有点像脑筋急转弯#xff0c;尽量让石头分成重量相同的两堆#xff08;尽可能相同#xff09;#xff0c;相撞之后剩下的石头就是最小的。明白这一点#xff0c;就与上一篇博客里的划分等和数组很相似。划分等和数组…一、动态规划DP Ⅳ
1、最后一块石头的重量II 1049
这题有点像脑筋急转弯尽量让石头分成重量相同的两堆尽可能相同相撞之后剩下的石头就是最小的。明白这一点就与上一篇博客里的划分等和数组很相似。划分等和数组是给定背包容量能不能恰好填满该背包这题是给定背包容量尽可能填满该背包。直接套用代码。
class Solution {
public:int lastStoneWeightII(vectorint stones) {int ss accumulate(stones.begin(), stones.end(), 0);int s ss / 2;vectorint dp(s 1);for(int stone : stones)for(int js; jstone; --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组合 targetleft 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两个选择所以递推方程为 d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i − 1 ] [ j − n u m s [ i ] ] dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]] dp[i][j]dp[i−1][j]dp[i−1][j−nums[i]]相应的一维为 d p [ j ] d p [ j − n u m s [ i ] ] dp[j] dp[j-nums[i]] dp[j]dp[j−nums[i]]。
class Solution {
public:int findTargetSumWays(vectorint 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;vectorint dp(s 1);dp[0] 1;for(int i0; inums.size(); i)for(int js; jnums[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(vectorstring strs, int m, int n) {vectorvectorint dp(m1, vectorint(n1));for(string str : strs){ // 遍历物品int one 0, zero 0;for(char ss : str){if(ss1)one;elsezero;}// 遍历背包for(int im; izero; --i)for(int jn; jone; --j)dp[i][j] max(dp[i-zero][j-one] 1, dp[i][j]);}return dp[m][n];}
};二、写在后面
难点在于将问题分析清楚理清如何转换成背包问题。第一题是给定背包容量尽可能装最多能装多少第二题是给定背包容量求装满背包的方法第三题是给定背包容量求装满背包最多有多少物品并且此背包比较特殊有两个维度。
