Skip to main content

3-13 198.打家劫舍

Date：2022-03-13 11:04:29

标签：

  • 动态规划

题目：198.打家劫舍 ( 中等😕 )​

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的 非负整数 数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例​

示例1

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例2

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析​

  • ❌ 暴力法

    • 双层for循环，步长为2
    • 边界条件
      • 只有一家，则最大金额为该家
      • 有两家，则最大金额为两家中的最大金额

  • 动态规划

    假设有k家，那么，此时要偷到最大金额，会有两种情况：

    • 偷第k家，那么就不能偷第k-1家，此时最大金额为第k家的金额加上k-2家的最大金额
    • 不偷第k家，那么此时最大金额为k-1家的最大金额

    所以，最大金额(P)为：

    ​ P(k) = Max( P(k-2)+nums[k] , P(k-1) )

    边界条件

    • 只有一家，则最大金额为该家
    • 有两家，则最大金额为两家中的最大金额

    时间和空间复杂度都是O(n)

题解​

注意：在LeetCode中打印日志，会增加执行时间（可能是两倍）

function rob(nums: number[]): number {
  const len = nums.length

  if (len == 1) {
    return nums[0]
  } else if (len == 2) {
    return Math.max(nums[0], nums[1])
  }

  const dep = []

  dep[0] = nums[0]
  dep[1] = Math.max(nums[0], nums[1])

  for (let i = 2; i < len; ++i) {
    dep[i] = Math.max(dep[i - 2] + nums[i], dep[i - 1])
  }

  return dep[len - 1]
}

使用

function main() {
  // const nums = [1, 2, 3, 1]
  const nums = [2, 7, 9, 3, 1]

  console.log('[]:', rob(nums))
}
main()

export {}