打家劫舍
House Robber
本机进度仅保存在当前浏览器
题目描述
你是一个小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被偷窃，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例：nums = [2, 7, 9, 3, 1]，输出 12（偷 2 + 9 + 1）。
解题思路
- 状态：dp[i] 为考虑前 i+1 间房能偷到的最高金额。第 i 间只有偷或不偷两种选择。
- 偷第 i 间则第 i-1 间不能偷，得 dp[i-2] + nums[i]；不偷则维持 dp[i-1]，取两者较大。
- 同样只需两个滚动变量；边界从"前两间"的最大值起步。
参考实现
查看参考实现Python · 建议先自行作答
def rob(nums):
# prev/cur 分别对应 dp[i-2] 与 dp[i-1]
prev = cur = 0
for x in nums:
prev, cur = cur, max(cur, prev + x)
return cur