wordpress怎么生成网站地图,室内设计联盟官方网站入口,宝安网站建设公司,苏州pc网站开发让石头分成重量相同的两堆#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;}
}题目链接
