手机网站跳转,谁有做那事的网站,asp手机网站统计代码,网络营销设计方案让石头分成重量相同的两堆#xff08;尽可能相同#xff09;#xff0c;相撞之后剩下的石头就是最小的。进一步转化成容量为重量总喝一半的背包最多可以装多少质量的石头。这样就转化成了背包问题。 最后求结果时#xff0c;我们所最多能装的时dp[target]#xff0c;那另一…让石头分成重量相同的两堆尽可能相同相撞之后剩下的石头就是最小的。进一步转化成容量为重量总喝一半的背包最多可以装多少质量的石头。这样就转化成了背包问题。 最后求结果时我们所最多能装的时dp[target]那另一半石头就是sum-dp[target]我们所求的就是(sum-dp[target])-dp[target]也就是sum-dp[target] * 2。
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for(int num:stones) sum num;int target sum/2;int[] dp new int[target 1];for(int i0;idp.length;i){dp[i] 0;}for(int i0;istones.length;i){for(int jtarget;jstones[i];j--){dp[j] Math.max(stones[i]dp[j-stones[i]],dp[j]);}}return sum-dp[target] * 2;}
}题目链接
