重量II"/>
动态规划:12最后一块石头的重量II
动态规划:12最后一块石头的重量II
1049. 最后一块石头的重量 II
分析
要使相撞过后的石头重量最小,我们只需要将石头分为重量相似的两堆就可以了
题目与动态规划:11分割等和子集有异曲同工之妙
五部曲
-
确定dp数组含义:dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。
可以回忆一下01背包中,dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。
相对于 01背包,本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
-
确定递归公式:dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
dp[j] = Math.max(dp[j], (dp[j - weight[i]] + value(i)))
-
dp数组初始化:dp[j] = 0
重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。
-
遍历顺序:先物后包,包要倒序
-
debug:打印dp数组
代码
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp数组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 - 2 * dp[target];}
}
- 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
- 空间复杂度:O(m)
总结
本题其实和动态规划:11分割等和子集几乎是一样的,只是最后对dp[target]的处理方式不同。
动态规划:11分割等和子集相当于是求背包是否正好装满,而本题是求背包最多能装多少。
更多推荐
动态规划:12最后一块石头的重量II
发布评论