湖北黄石网站建设,做图片素材的网站,网站开发主要内容,美图秀秀在线制作题目来源#xff1a;https://leetcode.cn/problems/last-stone-weight-ii/description/ C题解#xff08;思路来源代码随想录#xff09;#xff1a;本题其实就是尽量让石头分成重量相同的两堆#xff0c;相撞之后剩下的石头最小#xff0c;这样就化解成01背包问题了。
…题目来源https://leetcode.cn/problems/last-stone-weight-ii/description/ C题解思路来源代码随想录本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
动规五步曲
确定dp数组以及下标的含义。dp[j]表示容量这里说容量更形象其实就是重量为j的背包最多可以背最大重量为dp[j]。本题中石头的重量是 stones[i]石头的价值也是 stones[i] 可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]”确定递推公式。01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]); 本题则是dp[j] max(dp[j], dp[j - stones[i]] stones[i]);dp数组如何初始化。既然 dp[j]中的j表示容量那么最大容量重量就是所有石头的重量和。而我们要求的target其实只是最大重量的一半。确定遍历顺序。如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历举例推导dp数组
// 自己的版本
class Solution {
public:int lastStoneWeightII(vectorint stones) {int len stones.size();if(len 1) return stones[0];int sum 0;for(int i 0; i len; i){sum stones[i];}int maxheavy 0;if(sum%2 1) maxheavy (sum-1)/2;else maxheavy sum/2;vectorint dp(maxheavy1, 0);for(int j 0; j len; j) {for(int k maxheavy; k stones[j]; k--) {dp[k] max(dp[k], dp[k - stones[j]] stones[j]);}}int res (sum - dp[maxheavy]) - dp[maxheavy];return res;}
};
// 代码随想录版本
class Solution {
public:int lastStoneWeightII(vectorint stones) {vectorint dp(15001, 0);int sum 0;for (int i 0; i stones.size(); i) sum stones[i];int target sum / 2;for (int i 0; i stones.size(); i) { // 遍历物品for (int j target; j stones[i]; j--) { // 遍历背包dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - dp[target] - dp[target];}
};
