198. 打家劫舍
题目描述
一条街上有一排房子，nums[i] 是第 i 间房子里的现金，均为非负整数。
你打算在一晚之内偷这些房子。相邻两间房子的防盗系统是连通的：只要同一晚有两间相邻房子被闯入，就会报警。
在不触发报警的前提下，返回能偷到的最大金额。
示例 1
输入：nums = [1,2,3,1] 输出：4
解释：偷第 1 间（1）和第 3 间（3），共 4。
示例 2
输入：nums = [2,7,9,3,1] 输出：12
解释：偷第 1、3、5 间，金额为 2 + 9 + 1 = 12。
数据范围
1 <= nums.length <= 1000 <= nums[i] <= 400
解题思路
第 i 间房屋在偷与不偷之间取最大值：dp[i]=max(dp[i-1],dp[i-2]+nums[i])。
为什么正确
prev2、prev1 分别是处理到前两间和前一间时的最优金额。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
状态要代表“前缀最优”，不能只贪心选择当前最大房屋。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
prev2, prev1 = 0, 0
for money in nums:
prev2, prev1 = prev1, max(prev1, prev2 + money)
return prev1class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int money : nums) {
int cur = Math.max(prev1, prev2 + money);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution {
public:
int rob(vector<int>& nums) {
int prev2 = 0, prev1 = 0;
for (int money : nums) {
int cur = max(prev1, prev2 + money);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};func rob(nums []int) int {
prev2, prev1 := 0, 0
for _, money := range nums {
prev2, prev1 = prev1, max(prev1, prev2+money)
}
return prev1
}var rob = function(nums) {
let prev2 = 0, prev1 = 0;
for (const money of nums) {
[prev2, prev1] = [prev1, Math.max(prev1, prev2 + money)];
}
return prev1;
};function rob(nums: number[]): number {
let prev2 = 0, prev1 = 0;
for (const money of nums) {
[prev2, prev1] = [prev1, Math.max(prev1, prev2 + money)];
}
return prev1;
}