House Robber（打家劫舍）是 LeetCode 上的第 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 。

解题思路

这个问题可以使用动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示偷到第 i 个房子时能够获得的最大金额。

状态转移方程：

• 如果偷第 i 个房子，那么不能偷第 i-1 个房子，最大金额为 dp[i-2] + nums[i]。
• 如果不偷第 i 个房子，那么最大金额为 dp[i-1]。

所以，状态转移方程为：

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

初始条件：

• dp[0] = nums[0]，因为如果只有一个房子，最大金额就是那个房子的金额。
• dp[1] = max(nums[0], nums[1])，因为如果有两个房子，最大金额是这两个房子中金额较大的那个。

代码实现

以下是使用 Python 实现的动态规划解法：

def rob(nums): if not nums: return 0 n = len(nums) if n == 1: return nums[0]

dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])

return dp[-1]

print(rob([1,2,3,1])) # 输出：4 print(rob([2,7,9,3,1])) # 输出：12

优化空间复杂度

我们可以进一步优化空间复杂度，因为每次状态转移只依赖于前两个状态，所以可以用两个变量来代替数组。

def rob(nums): if not nums: return 0 n = len(nums) if n == 1: return nums[0]

prev2 = nums[0]
prev1 = max(nums[0], nums[1])

for i in range(2, n):
    current = max(prev1, prev2 + nums[i])
    prev2 = prev1
    prev1 = current

return prev1

print(rob([1,2,3,1])) # 输出：4 print(rob([2,7,9,3,1])) # 输出：12

总结

这道题通过动态规划的思想，将问题分解为子问题，逐步求解。通过状态转移方程和初始条件的设定，能够有效地求解出最大偷窃金额。优化后的解法在空间复杂度上更加高效，适用于大规模输入的情况。

希望这个详细的解答对你有所帮助！如果有更多问题，欢迎继续提问。