leetcode 刷题 log day 48（打家劫舍问题

• 198. 打家劫舍
  【思路】当前房屋偷不偷，取决于上一个房间和上上个房间的状态，上一个房间偷了，这个房间就不能偷，所以也属于动规问题。

  • 确定递推公式含义：dp[i] 表示考虑完第 i 个房间时偷盗的最大金额；
  • 确定递推公式： 考虑第 i 个房间偷不偷，取决于第 i - 1 个房间偷不偷，假如上一个房间没有偷，那么最大金额就是上上个房间的金额 + 第 i 个房间的金额： dp[i] = dp[i - 2] + nums[i]，如果上一个房间偷了，那么第 i 个房间就不偷：dp[i] = dp[i - 1]，那么最大金额就是取两者的较大值；
  • 初始化： 初始前两个房间：dp[0] = nums[0]，dp[1] = Math.max(nums[0], nums[1])；
  • 遍历顺序： 因为当前值是由前两个值推导出来的，所以肯定是从前往后遍历；

  var rob = function(nums) {
    let dp = [nums[0], Math.max(nums[0], nums[1])];
  
    for (let i = 2; i < nums.length; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[nums.length - 1];
  };
  1
  2
  3
  4
  5
  6
  7
  8

• 213. 打家劫舍II
  【思路】这道题比上一道题做了一个条件，要考虑偷第一家，不偷最后一家和不偷第一家，偷最后一家两种情况，所以分开两次计算最后取较大者。

  var rob = function(nums) {
    if (nums.length === 1) return nums[0];
  
    const robRange = (start, end) => {
      if (start === end) return nums[start];
      let dp = new Array(nums.length).fill(0);
      dp[start] = nums[start];
      dp[start + 1] = Math.max(nums[start], nums[start + 1]);
      
      for (let i = start + 2; i <= end; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
      }
      return dp[end];
    }
  
    let res1 = robRange(0, nums.length - 2),  // 考虑偷第一家，不偷最后一家
        res2 = robRange(1, nums.length - 1);  // 考虑不偷第一家，偷最后一家
    return Math.max(res1, res2);
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 337. 打家劫舍III
  【思路】这道题把数组换成了二叉树，遍历二叉树要用到递归。因为要通过返回的值进行计算，所以使用后序遍历。动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。（为什么不记录每个节点偷和不偷的金额？因为递归会记录当前层的值，不用我们使用 dp 来记录，只记录当前层就可以）。
  递归三部曲：

  • 确定递归函数的返回值和参数：返回值就是当前层的偷和不偷的金额，参数就是当前节点；
  • 确定终止条件：当节点为 null 时无论偷不偷金额都是 0；
  • 确定单层递归逻辑：如果偷了当前节点，那么左右子节点就不能偷 val1 = node.val + left[0] + right[0]，如果不偷当前节点，就可以考虑偷左节点或者右节点取最大值 val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1])；
  • dp 数组以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

  var rob = function(root) {
    const robTrackback = node => {
      if (!node) return [0, 0];
      // 遍历左子树
      let left = robTrackback(node.left);
      let right = robTrackback(node.right);
  
      // 不偷当前节点，左右子节点可以选择偷或者不偷，取最大值
      let donot = Math.max((left[0]), left[1]) + Math.max(right[0], right[1]);
      // 偷当前节点，那么左右子节点都不能偷
      let dorob = node.val + left[0] + right[0];
      return [donot, dorob];
    }
  
    const res = robTrackback(root);
    return Math.max(...res);
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

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