198. 打家劫舍

难度：🟡 Medium | 标签：动归 | 状态：⬜ LeetCode 链接

思路

dp[i] = max(dp[i-1], dp[i-2] + nums[i])：

• 不偷 i：继承 dp[i-1]
• 偷 i：dp[i-2] + nums[i]

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 滚动两变量 prev1 / prev2
• 213（环形打家劫舍）：拆成两段——「偷第一家」和「不偷第一家」各跑一次
• 337（树形打家劫舍）：树形 DP