【leetcode（力扣及198及打家劫舍及题解及算法题）】在 LeetCode 的众多算法题目中，第 198 题“打家劫舍”（House Robber）是一个非常经典的问题。它不仅考察了动态规划的基本思想，还能够帮助我们理解如何在特定条件下做出最优决策。本文将对这道题进行详细解析，并提供一个高效的解决方案。
一、题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每个房屋都存放有一定金额的钱。但你不能同时偷窃相邻的两间房屋。例如，如果你偷了第 1 间房，那么你就不能偷第 2 间；但你可以偷第 3 间。你的目标是偷取尽可能多的钱。
输入：一个整数数组，表示每间房屋内的金额。
输出：你能偷到的最高金额。
二、解题思路
这是一道典型的动态规划问题。我们可以使用动态规划的方法来解决这个问题，因为每一步的选择都会影响后续的结果，而我们需要找到全局最优解。
1. 状态定义
设 `dp[i]` 表示前 `i` 间房屋能偷到的最大金额。
2. 状态转移方程
对于第 `i` 间房屋，有两种选择：
- 偷第 i 间：则不能偷第 i-1 间，此时最大金额为 `dp[i-2] + nums[i]`
- 不偷第 i 间：则最大金额为 `dp[i-1]`
因此，状态转移方程为：
```
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
```
3. 初始条件
- 当没有房屋时，最大金额为 0 → `dp[0] = 0`
- 当只有一间房屋时，只能偷这一间 → `dp[1] = nums[0]`
三、代码实现
以下是使用 Python 实现的动态规划版本：
```python
def rob(nums):
n = len(nums)
if n == 0:
return 0
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]
```
四、优化空间复杂度
由于每次计算只依赖于前两个状态，我们可以将空间复杂度从 O(n) 优化到 O(1)，只需保存前两个状态的值即可。
```python
def rob_optimized(nums):
prev = curr = 0
for num in nums:
temp = curr
curr = max(curr, prev + num)
prev = temp
return curr
```
五、测试样例
输入： `[1,2,3,1]`
输出： `4`
解释：偷第 1 间和第 3 间，总金额为 1+3=4。
输入： `[2,7,9,3,1]`
输出： `12`
解释：偷第 1 间和第 3 间，总金额为 2+9=11；或者偷第 2 间和第 4 间，总金额为 7+3=10。最优为 12。
六、总结
LeetCode 第 198 题“打家劫舍”是一道典型的动态规划题目，通过合理地定义状态和转移方程，可以高效地求解出最优解。本题的核心在于理解“不能连续偷”的限制条件，并据此设计状态转移逻辑。
掌握这类题目的解法，不仅能提升你的算法能力，还能在实际开发中处理类似的问题，如资源分配、路径选择等场景。
---
希望这篇题解对你有所帮助！如需更多 LeetCode 题目解析，欢迎继续关注。
