- 最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
https://programmercarl.com/1049.最后一块石头的重量II.html
这三体=题都没啥思路
/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeightII = function(stones) {
let sum = 0;
for (let i=0;i<stones.length;i++) {
sum+=stones[i];
}
let target = Math.floor(sum/2);
const dp = new Array(target+1).fill(0);
for (let i=0;i<stones.length;i++) {
for (let j=target;j>=stones[i];j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum-dp[target] - dp[target];
};
- 目标和
大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.目标和.html
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let sum = 0;
for (let i=0;i<nums.length;i++) {
sum+=nums[i];
}
if (Math.abs(target)>sum) {
return 0;
}
if ((sum+target)%2===1) {
return 0;
}
let left = (sum+target)/2;
const dp = new Array(left+1).fill(0);
dp[0] = 1;
for (let i=0;i<nums.length;i++) {
for (let j=left;j>=nums[i];j--) {
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
};
474.一和零
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.一和零.html
/**
* @param {string[]} strs
* @param {number} m
* @param {number} n
* @return {number}
*/
var findMaxForm = function(strs, m, n) {
const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
for (let str of strs) {
let x = 0;
let y = 0;
for (let k=0;k<str.length;k++) {
if (str[k] === '0'){
x++;
} else {
y++;
}
}
for (let i=m;i>=x;i--) {
for(let j=n;j>=y;j--) {
dp[i][j] = Math.max(dp[i][j], dp[i-x][j-y]+1);
}
}
}
return dp[m][n];
};