leetcode 刷题 log day 43

• 1049. 最后一块石头的重量 II
  【思路】这道题的难点在于怎么和背包问题扯上关系。从数组中任意选两个元素，粉碎石头添加剩余的量，直到剩余的重量最小，就可以把石头尽可能的重量平均分成两堆，子集之和相减，留下的就是最小的重量。这样，就和背包问题扯上关系了，先求元素总和 sum，再除以 2，就是子集近似要满足的值，也是背包的容量。最后把两个自己的和相减就是剩余最小重量。

  var lastStoneWeightII = function(stones) {
    let len = stones.length,
        sum = (stones.reduce((p, v) => p + v)),
        halfSum = Math.floor(sum / 2),
        dp = new Array(halfSum + 1).fill(0);
    
    for (let i = 0; i < len; i++) {
      for (let j = halfSum; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
      }
    }
    return Math.abs((sum - dp[halfSum]) - dp[halfSum]);
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 494. 目标和
  【思路】难点在于怎么和背包问题联系起来，假如我们把元素分成两个子集，左边为正数，右边为负数，两个子集相减看是否满足 target，那么就可以得到两个式子：left + right = sum left - right = targrt，整理得：left = (sum + right) / 2，这样，就又转换成了背包问题，看有几种方法能够装满背包，假如出现 sum 和 target 的和不是偶数呢，那么就说明，没有满足条件的子集，就直接返回 0。

  var findTargetSumWays = function(nums, target) {
    let sum = nums.reduce((s, n) => s + n);
    if (Math.abs(target) > sum) return 0;
    if ((target + sum) % 2) return 0;
    let halfSum = Math.floor((sum + target) / 2),
        dp = new Array(halfSum + 1).fill(0);
   
  
    dp[0] = 1;
  
    for (let i = 0; i < nums.length; i++) {
      for (let j = halfSum; j >= nums[i]; j--) {
        dp[j] += dp[j - nums[i]];
      }
    }
    return dp[halfSum];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 474. 一和零
  【思路】这道题是真的不会！看了题解也不会！甚至不知道哪不会！就很神奇呜呜呜（暴风哭泣
  直接看题解吧

  var findMaxForm = function(strs, m, n) {
    let dp = new Array(m + 1).fill().map(() => Array(n + 1).fill(0)),
        zeroNum, oneNum;
    
    for (let str of strs) {
      zeroNum = 0;
      oneNum = 0;
      for (let s of str) {
        if (s === '0') zeroNum++
        else oneNum++;
      }
  
      for (let i = m; i >= zeroNum; i--) {
        for (let j = n; j >= oneNum; j--) {
          dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
      }
    }
  
    return dp[m][n];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

参考代码随想录：https://www.programmercarl.com/