| 题目链接 | 198. 打家劫舍 |
|---|---|
| 思路 | 入门动态规划-“打家劫舍”系列 |
| 题解链接 | 【视频讲解】动态规划入门：从记忆化搜索到递推（Python/Java/C++/Go/JS） |
| 关键点 | 无 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(n)\)或者\(O(1)\) |
代码实现（DFS）：
class Solution:
def rob(self, nums: List[int]) -> int:
@cache
def dfs(i):
if i < 0:
return 0
return max(dfs(i-1), dfs(i-2) + nums[i])
return dfs(len(nums)-1)
代码实现（递推）：
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0] * (len(nums) + 2)
for i, x in enumerate(nums):
dp[i+2] = max(dp[i+1], dp[i]+x)
return dp[-1]
代码实现（空间优化）：
class Solution:
def rob(self, nums: List[int]) -> int:
dp0 = dp1 = 0
for x in nums:
dp0, dp1 = dp1, max(dp1, dp0 + x)
return dp1