动态规划 part05
- 1049. 最后一块石头的重量 II
- 解题思路
- 494. 目标和
- 解题思路
- 474.一和零
- 解题思路
- 总结
详细布置
1049. 最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
题目链接： 1049. 最后一块石头的重量 II
视频讲解： 1049. 最后一块石头的重量 II
文章讲解： 1049. 最后一块石头的重量 II
解题思路
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
动规五步曲：
- 确定dp数组以及下标的含义
相对于 01背包，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]” - 确定递推公式
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); - dp数组如何初始化
既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。
因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。
而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。
当然也可以把石头遍历一遍，计算出石头总重量 然后除2，得到dp数组的大小。
接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。 - 确定遍历顺序
在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！ - 举例推导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];
}
}
494. 目标和
大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
题目链接： 494. 目标和
视频讲解： 494. 目标和
文章讲解： 494. 目标和
解题思路
为什么是01背包呢？
因为每个物品（题目中的1）只用一次！
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
可以记住，在求装满背包有几种方法的情况下，递推公式一般为：
dp[j] += dp[j - nums[i]];
// 动态规划
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(target < 0 && sum < -target) return 0;
if((target + sum) % 2 != 0) return 0;
int size = (target + sum) / 2;
if(size < 0) size = -size;
int[] dp = new int[size + 1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++){
for(int j = size; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[size];
}
}
474.一和零
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
题目讲解： 474.一和零
视频讲解： 474.一和零
文章讲解： 474.一和零
解题思路
这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。
// 动态规划
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
int oneNum, zeroNum;
for(String str : strs){ // 先遍历物品
oneNum = 0;
zeroNum = 0;
for(char ch : str.toCharArray()){
if(ch == '0'){
zeroNum++;
}else{
oneNum++;
}
}
// 再遍历背包 倒序
for(int i = m; i >= zeroNum; i--){
for(int j = n; j >= oneNum; j--){
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum]);
}
}
}
return dp[m][n];
}
}
总结
不少同学刷过这道题，可能没有总结这究竟是什么背包。
此时我们讲解了0-1背包的多种应用，
纯 0 - 1 背包 是求 给定背包容量 装满背包 的最大价值是多少。
416. 分割等和子集 是求 给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量 II 是求 给定背包容量，尽可能装，最多能装多少
494. 目标和 是求 给定背包容量，装满背包有多少种方法。
本题是求 给定背包容量，装满背包最多有多少个物品。
