身为菜鸡的感慨:这是怎么想到用背包问题的啊!巧夺天工啊!
思路:
一堆子石头,两个两个一起碰,求最后剩下的最小的石头重量dp数组的定义:容量为j的背包可以容纳的石头的最大重量,剩下的石头重量就是sum - dp【sum / 2】 石头一起碰撞,两者相减,就是最后剩下的最小的石头的重量,比较典型的01背包的问题。
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 i = 0;i < stones.length;i++){ for(int j = target;j >= stones[i];j--){ dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]); } } return (sum - dp[target]) - dp[target]; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)