1049. 最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i : stones) sum += i;
int n = sum / 2;
int m = stones.length;
int[] dp = new int[n+1];
dp[0] = 0;
for(int i = 0; i < m; i ++ ){
for(int j = n; j >= stones[i]; j --){
dp[j] = Math.max(dp[j], stones[i] + dp[j- stones[i]]);
}
}
return sum - dp[n] * 2;
}
}
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
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i : nums) sum += i;
if((sum - target) % 2 != 0) return 0;
int left = (sum - target) / 2;
int[] dp = new int[left+1];
dp[0] = 1;
for(int i = 0; i < nums.length; i ++){
for(int j = left; j >= nums[i]; j --){
dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[left];
}
}
java.lang.NegativeArraySizeException: -20
at line 7, Solution.findTargetSumWays
at line 56, __DriverSolution__.__helper__
at line 89, __Driver__.main
最后执行的输入
添加到测试用例
nums =
[2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53]
target =
1000
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i : nums) sum += i;
if((sum - target) % 2 != 0) return 0;
if((sum - target) < 0) return 0;
int left = (sum - target) / 2;
int[] dp = new int[left+1];
dp[0] = 1;
for(int i = 0; i < nums.length; i ++){
for(int j = left; j >= nums[i]; j --){
dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[left];
}
}
474.一和零
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
dp[0][0] = 0;
for(int i = 0; i < strs.length; i ++ ){
int x = 0, y = 0;
for(int k = 0; k < strs[i].length(); k ++){
if(strs[i].charAt(k) == '0') x ++;
else y ++;
}
for(int p = m; p >= x; p --){
for(int q = n; q >= y; q --){
dp[p][q] = Math.max(dp[p][q], dp[p-x][q-y] + 1);
}
}
}
return dp[m][n];
}
}
