亦庄网站建设,网站开发代理商,外贸做哪个网站平台,设计方案介绍题目描述 原题链接#xff1a;1049. 最后一块石头的重量 II
解题思路
本题要找的是最小重量#xff0c;我们可以将石头划分成两个集合#xff0c;当两个集合的重量越接近时#xff0c;相减后#xff0c;可达到的装量就会是最小#xff0c;此时本题的思路其实就类似于 4…题目描述 原题链接1049. 最后一块石头的重量 II
解题思路
本题要找的是最小重量我们可以将石头划分成两个集合当两个集合的重量越接近时相减后可达到的装量就会是最小此时本题的思路其实就类似于 416. 分割等和子集动态规划二维数组滚动数组 。
首先对所有石头的总重量求和然后设置一个变量target表示总重量之和的二分之一使用动态规划的方式划分出一个集合之和dp[target]然后用总重量之和减去dp[target]就得到对石头的另一个集合划分之和。二者相减就是最小重量。
动态规划五步曲
1dp[j]含义 在背包容量为j的条件下可装入的最大物品重量总和。
2递推公式 dp[j] max(dp[j], dp[j - stones[i]] stones[i])
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sumNums 0;for(int i 0; i stones.size(); i) sumNums stones[i];int target sumNums / 2;int dp[1501] {0};int n stones.size();for(int i 0; i n; i) {for(int j target; j stones[i]; j--) {dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return abs(sumNums - dp[target] - dp[target]);}
};参考文章1049. 最后一块石头的重量 II
