题目描述
LeetCode 198 — 打家劫舍 (Medium)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统——如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的整数数组 nums，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1：
- 输入：
nums = [1,2,3,1] - 输出：
4 - 解释：偷窃第 1 间和第 3 间房屋（金额 = 1 + 3 = 4），跳过第 2 间。
示例 2：
- 输入：
nums = [2,7,9,3,1] - 输出：
12 - 解释：偷窃第 1、3、5 间房屋（金额 = 2 + 9 + 1 = 12）。
约束：
1 <= nums.length <= 1000 <= nums[i] <= 400
求解思路
面对一排房屋，每间都要做一个二选一的决定：抢，还是不抢。如果抢了第 i 间，那第 i-1 间就不能碰；如果不抢第 i 间，那前 i-1 间怎么抢都行。换句话说，走到第 i 间屋子时的最优解，只取决于前两步的状态——抢第 i-1 间时的最优值，和不抢第 i-1 间（即前 i-2 间的最优值加上第 i 间的金额）哪个更大。
这就自然地引出了动态规划。设 dp[i] 为考虑前 i 间房屋能偷到的最高金额，状态转移方程是 dp[i] = max(dp[i-1], nums[i] + dp[i-2])。含义很直观：要么跳过第 i 间，沿用前一间的最优解；要么抢第 i 间，加上前两间的最优解。
初始条件也容易确定：只有一间屋子时直接抢它，dp[1] = nums[0]；有两间屋子时抢金额大的那间，dp[2] = max(nums[0], nums[1])。
注意到每次计算只依赖前两个状态值，完全不需要维护整个数组，用两个滚动变量 first 和 second 就够了，空间从 O(n) 压到 O(1)。
解法：动态规划
package hot100;
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1) return nums[0];
else if(n == 2) return Math.max(nums[1],nums[0]);
else{
int first = nums[0];
int second = Math.max(nums[1],nums[0]);
for(int i = 2; i < n; i++){
int third = Math.max(second, nums[i] + first);
first = second;
second = third;
}
return second;
}
}
}
class Solution:
def rob(self, nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
elif n == 2:
return max(nums[0], nums[1])
else:
first = nums[0]
second = max(nums[0], nums[1])
for i in range(2, n):
third = max(second, nums[i] + first)
first = second
second = third
return second
复杂度： 时间 O(n)；空间 O(1)，仅使用两个滚动变量。