打家劫舍系列

发表于2024-07-08更新于2024-07-08

打家劫舍系列

打家劫舍（198）

https://leetcode.cn/problems/house-robber/description/

图 0

思路
五部曲

  • 1、dp[i] 考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

  • 2、递推公式：
    偷：dp[i] = dp[i-2] + num[i]，不偷：dp[i] = dp[i-1],因此dp[i] = max(dp[i-2] + num[i],dp[i] = dp[i-1])

  • 3、初始化：
    从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

    从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

  • 4、遍历：i从2到最后一个房间

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

打家劫舍（213）

https://leetcode.cn/problems/house-robber-ii/description/

图 1

思路
对于一个数组，成环的话主要有如下三种情况：

  • 1、首尾均不考虑
  • 2、考虑首，不考虑尾
  • 3、考虑尾，不考虑首
    情况2和3包含了情况1，因此只需取情况2和3的最大值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var rob = function(nums) {
  let n = nums.length
  if (n===1) result = nums[0]
  else{
    result1 = robRange(nums,1,n-1)
    result2 = robRange(nums,0,n-2)
    result = Math.max(result1,result2)
  }
  function robRange(nums,start,end){
    let dp = Array(end-start+2).fill(0)
    dp[start] = nums[start]
    dp[start+1] = Math.max(nums[start],nums[start+1])
    console.log(start,end)
    for (let i=start+2;i<=end;i++){
      dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])
    }
    console.log(dp)
    return dp[end]
  }
  return result
};

打家劫舍（337）

https://leetcode.cn/problems/house-robber-iii/description/

图 2

思路
数据结构变成个二叉树了，投了父节点就不能考虑子节点了，而是要考虑孙子节点

  • 每个节点有一个一维dp数组，数组长度为2，dp[0]表示不偷所获金钱的最大值，dp[1]表示偷所获金钱的最大值。

  • 递归三部曲

    • 确定参数，robtree(root)返回dp数组
    • 终止条件，if(cur == null) return [0,0]
    • 遍历顺序是后序遍历，因为父的值需要依靠孩子的值决定

  • 递归五部曲

    • 1、dp[0]表示不偷所获金钱的最大值，dp[1]表示偷所获金钱的最大值。
    • 2、递推公式dp[0] = max(leftdp[0],leftdp[1]) + max(rightdp[0],rightdp[1]) ,dp[1] = cur.val + leftdp[0] + rightdp[0]
    • 3、初始化均为0
    • 4、遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var rob = function(root) {
  //递归后续遍历二叉树
  const robtree = (rootnode)=>{
    let cur = rootnode
    if(cur===null) return [0,0]
    let leftdp = robtree(cur.left)
    let rightdp = robtree(cur.right)
    let val0 = Math.max(leftdp[0],leftdp[1]) + Math.max(rightdp[0],rightdp[1])
    let val1 = cur.val + leftdp[0] + rightdp[0]
    return [val0,val1]
  }
  //这里解构的时候容易出错
  let [result0,result1] = robtree(root)
  // console.log(result0,result1)
  return Math.max(result0,result1)
};