第九章 动态规划 part05
● 1049. 最后一块石头的重量 II
● 494. 目标和
● 474.一和零
详细布置
1049. 最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
494. 目标和
大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
474.一和零
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
day42
最后一块石头的重量2
//把石头分成重量相近的两堆,然后一边取一个放进去磨,左边石头磨完了再从左边取一个放进去和右边磨过的石头一起磨,这样最后剩下的时候头就是abs(左堆重量- 右堆重量)
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for( int num : stones){
sum += num;
}
int target = sum >> 1 ;
int[] dp = new int[target + 1];
//初始化
//for(int i = stones[0]; i <= target; i++){//这里i = target也需要初始化
// dp[i] = stones[0];
//}
//for( int i = 1; i < stones.length ; i++){
for( int i = 0; i < stones.length ; i++){//对一维来说,第一行的初始化可以放进循环,因为不涉及dp[i - 1][j],所以i可以为0
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];
}
}
目标和
dp[i][j]表示用0~i号元素装满容量j,的方法,的个数
//为了理解一维数组,在idea中的调试代码
class demo02 {
public static void main(String[] args) {
int[] nums = {0,0,0};
int target = 0;
findTargetSumWays(nums,target);
}
public static int findTargetSumWays(int[] nums, int target) {
//分成两组left和right,left - right = target即可,又因为left+right = sum,消去right,left = (sum + target)/2
//dp[i][j]表示从物品0到i去选,能组成容量j的 方法 有多少种
//不放物品i和放物品i两种情况推出来:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]](也就是留出放j的空间去)
int sum = 0;
for(int i : nums){
sum += i;
}
if((sum + target ) % 2 != 0) return 0;
if( sum < Math.abs(target) ) return 0;
int bagweight = sum + target >> 1;
int[][] dp = new int[nums.length][bagweight + 1];
//初始化
//第一行,只有nums[0] == j的时候,以及j == 0的时候,为1,其他都为0
//我们把dp[0][0]留给列去初始化,因为nums[0]是0的时候dp[0][0]是2
//对于一维数组来说,他的第一行初始化可以自己赋值,dp[0][0]是1还是2,也可以直接交给for里面i=0,但是初始化之前依然要把dp[0]赋值为0
//这是因为相当于是从[1,0,0,0]去初始化的i = 0这一行,如果第一个nums[0]==0,i=0那一行就是[2,0,0,0]
//一维数组可以避免非常麻烦的初始化
if(nums[0] <= bagweight) dp[0][nums[0]] = 1;//记得数组下标都需要判断一下
//第一列,什么都不放这一种方法,或者数组里面有0
//for(int i = 0; i < nums.length; i++){//这个初始化忽略了数组中可能有0的情况
// dp[i][0] = 1;
//}
int numZeros = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 0) {
numZeros++;
}
dp[i][0] = (int) Math.pow(2, numZeros);
}
//for(int i = 0; i < nums.length; i++){//这个初始化忽略了数组中可能有0的情况
// dp[i][0] = 1;
//}
for(int i = 1; i < nums.length ; i++) {
for (int j = 1; j <= bagweight; j++) {
if (j < nums[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
printall(dp);
return dp[nums.length - 1][bagweight];
}
public static void printall(int[][] dp){
int numslength = dp.length;
int weight = dp[0].length;
for(int i = 0; i < numslength ; i++) {
for (int j = 0; j < weight; j++) {
System.out.print(dp[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
}
一和零
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//背包有两个容量mn
int[][] dp = new int[m+1][n+1];
//初始化都为0
//先遍历物品再遍历背包
for( String str : strs){
int x = 0;
int y = 0;
for(char ch : str.toCharArray()){
if(ch == '0') x++;
else y++;
}
for(int i = m; i >= x; i--){
for(int j = n; j >=y; j--){
dp[i][j] = Math.max( dp[i][j], dp[i-x][j-y] + 1);
}
}
}
return dp[m][n];
}
}
感谢大佬分享:
代码随想录-算法训练营day42【动态规划05：最后一块石头的重量II、目标和、一和零】-****博客