代码随想录day42

1049. 最后一块石头的重量 II

https://leetcode.cn/problems/last-stone-weight-ii/
这个自己还是没想出来01背包对应。
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
stones = [2,7,4,1,8,1]也就是sum=23，2+7+1+1=11，4+8=12，差值为1。

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int i=0;i<stones.length;i++){sum+=stones[i];}int[] dp=new int[sum/2+1];for(int i=0;i<stones.length;i++){for(int j=sum/2;j>=stones[i];j--){dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}return  sum-2*dp[sum/2];}
}

494. 目标和

https://leetcode.cn/problems/target-sum/
这个更难想到怎么和01背包问题结合了，target是一个差值，但±怎么判定呢。
x-(sum-x)=target;——>x=(target+sum)/2;
这个真的好难理解啊

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];//如果target过大 sum将无法满足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. 一和零

https://leetcode.cn/problems/ones-and-zeroes/
这个也很难想到。
将m和n作为背包容量定义二维数组。

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];int x,y;for(str:strs){x=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];}
}