Skip to content

打家劫舍

· 5 min

题目#

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

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

示例 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 。

解题思路

这道题其实和上一道凑零钱的题目比较相似，我们把小偷能偷到的 最高金额 视为最优解。关键限制在于：两间相邻房子不可同时被偷。该问题可以被分解为如下的两个子问题：

  • 如果选择偷第 i 间房，那么 i - 1 间房就不能偷，只能加上偷到 i - 2 间房子的最高金额
  • 如果选择不偷第 i 间房，偷到第 i - 1 间房的最大金额就是最终的最高金额

这两个子问题的最优解组合出来就是整个问题的最优解

🙋该题目是否具备动态规划的三个特征？

  1. 最优子结构

    • 选择偷第 i 间房，就只能加上“偷到第 i - 2 间房”的最高金额
    • 不偷第 i 间房，那么就直接等于“偷到 i - 1 间房”的最高金额

  2. 重叠子问题

  3. 存储子问题解

状态转移方程

使用一个一维数组来存储能偷到的最高金额。例如 dp[i] 代表从下标 0 到 i + 1 间房中，能够偷到的最大金额。

  • 初始状态

    • dp[0] = nums[0] ，dp[0] 代表只能偷一间，那么只有一间房的时候，最高金额就是存放金额数组的第一个值。
    • dp[1]，代表有两间房，dp[1] = max(nums[0], num[1])，选择偷金额较大的那间房

  • 因此状态转移方程：

    dp[i]=max⁡(dp[i−1], dp[i−2]+nums[i])dp[i] = \max\Bigl( dp[i-1],\, dp[i-2] + \text{nums}[i]\Bigr)

    dp[i-1] 代表偷到 i-1 间房的最大金额，dp[i-2]+nums[i] 代表偷到 i-2 间房的最大金额加上当前这间的金额，看谁大就取谁的值，然后记录为当前偷到第 i 间房能获取到的最大金额。

代码实现

  1. 表格法
/**
 * 打家劫舍 - 表格法 (Bottom-Up)
 * @param {number[]} nums - 每个房屋中存放的金额
 * @return {number}       - 能偷窃到的最高金额
 */
function rob(nums) {
  const n = nums.length
  if (n === 0) return 0
  if (n === 1) return nums[0]


  // 创建 dp 数组，用于存储偷到每间房的最高金额
  // 数组第几项就代表偷到第几间房的最大金额
  // dp[0] - 偷到第1间房
  // dp[1] - 偷到第2间房
  // .....
  const dp = new Array(n)


  // 初始条件
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])


  // 状态转移，进行dp数组的填充
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  }


  return dp[n - 1]
}
  1. 记忆化搜索
/**
 * 打家劫舍 - 表格法 (Bottom-Up)
 * @param {number[]} nums - 每个房屋中存放的金额
 * @return {number}       - 能偷窃到的最高金额
 */
function rob(nums) {
  const n = nums.length
  if (n === 0) return 0
  if (n === 1) return nums[0]


  // 创建 dp 数组，用于存储偷到每间房的最高金额
  // 数组第几项就代表偷到第几间房的最大金额
  // dp[0] - 偷到第1间房
  // dp[1] - 偷到第2间房
  // .....
  const dp = new Array(n)


  function helper(i) {
    if (i < 0) return 0


    // 如果之前已经计算过了，直接返回对应的值
    if (dp[i] !== undefined) return dp[i]


    if (i === 0) {
      dp[0] = nums[0]
      return dp[0]
    }


    if (i === 1) {
      dp[1] = Math.max(nums[0], nums[1])
      return dp[1]
    }


    const result = Math.max(helper(i - 1), helper(i - 2) + nums[i])
    dp[i] = result
    return result
  }


  return helper(n - 1)
}

-EOF-