重庆网站设计生产厂家,php做网站教程,网站上传空间的ip地址,网站前台如何刷新1049. 最后一块石头的重量 II#xff08;题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台#xff09;
思路#xff1a;把全部石头重量加起来#xff0c;然后除以二#xff0c;就等于背包的最大容量。然后就可以按照背包问题…1049. 最后一块石头的重量 II题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路把全部石头重量加起来然后除以二就等于背包的最大容量。然后就可以按照背包问题做再将石头总质量减去背包最大容量得到的差减去背包里面的值就是可以得到的最小结果。
int lastStoneWeightII(vectorint stones) {int sum accumulate(stones.begin(), stones.end(), 0);int target sum/2;vectorint dp(target1, 0);for(int i0; istones.size(); i){for(int jtarget; jstones[i]; j--){dp[j] max(dp[j], dp[j-stones[i]]stones[i]);}}return (sum - dp[target]) - dp[target];
}
494. 目标和题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路乍一看还以为是个排列组合题目想用回溯法来做但是结果会超时。所以还是用dp做关键在于dp的构造细想其实可以得到这个式子left-righttargt, leftrightsum可以推出left(sumtarget)/2这就好办了left即为我们的背包最大容量。dp[left]即为我们要求的最终结果。但此题与其他不同的是他不是每次都去比较拿最大值而是一直做加法我的理解是实际还是做的排列组合
int findTargetSumWays(vectorint nums, int target) {int sum accumulate(nums.begin(), nums.end(), 0);if((sumtarget)%21) return 0;if(abs(target)sum) return 0;int bagSize (targetsum)/2;vectorint dp(bagSize1, 0);dp[0] 1;for(int i0; inums.size(); i){for(int jbagSize; jnums[i]; j--){dp[j] dp[j-nums[i]];}}return dp[bagSize];
}
474. 一和零题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路可以看作是两个背包合一起要装一起装要不都不装。
int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1, vectorint(n1, 0));for(string str : strs){int zeroNum0, oneNum0;for(char ch : str){if(ch0) zeroNum;else oneNum;}for(int im; izeroNum; i--){for(int jn; joneNum; j--){dp[i][j] max(dp[i][j], dp[i-zeroNum][j-oneNum] 1);}}}return dp[m][n];
}
