- 最后一块石头的重量 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];
};
