题目

给定一个非负整数数组，表示每间房屋存放的金额。不能偷相邻的房屋，问最多能偷多少钱。

题目分析

这题很适合练“当前元素选或不选”的动态规划模型。

当考虑第 i 个位置时：

  • 选它：那就不能选 i-1
  • 不选它：那就沿用前一个状态

方法一：直觉解法

最朴素的思路通常是递归枚举，但会有大量重复子问题。

方法二：优化思路

设 dp[i] 表示考虑前 i 间房屋时能获得的最大金额，则：

1dp[i] = max(dp[i-1], dp[i-2] + nums[i])

含义非常直接：

  • 不偷当前房屋：答案是 dp[i-1]
  • 偷当前房屋：答案是 dp[i-2] + nums[i]

Go 实现

 1func rob(nums []int) int {
 2    if len(nums) == 0 {
 3        return 0
 4    }
 5    if len(nums) == 1 {
 6        return nums[0]
 7    }
 8
 9    prev2, prev1 := nums[0], max(nums[0], nums[1])
10    for i := 2; i < len(nums); i++ {
11        cur := max(prev1, prev2+nums[i])
12        prev2 = prev1
13        prev1 = cur
14    }
15    return prev1
16}
17
18func max(a, b int) int {
19    if a > b {
20        return a
21    }
22    return b
23}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

易错点

  • 空数组和单元素数组要单独处理
  • dp[i-2] + nums[i] 表示的是“选当前”而不是“选前一个”

我的复盘

这题让我把“状态压缩”理解得更具体了：并不是所有 DP 都要保留整张表，关键是看当前状态到底依赖几个历史状态。