打家劫舍 图解题解

打家劫舍的约束到底是什么

数组 nums 里每个数是一户人家的现金，你可以任选若干家下手，唯一的限制是不能偷相邻的两家，求能拿到的最大总金额。换句话说，这是在数组里选一批互不相邻的数，让它们的和最大。难点全在「相邻互斥」上：选了这家，左右两家就自动作废。

为什么挑钱多的先偷这种贪心不行

直觉做法是贪心：哪家钱多偷哪家。但金额大的那家可能正好卡在两户中等人家中间，偷了它就同时废掉两边，总和反而更小——局部最优会锁死全局最优。另一头，把所有「互不相邻的选法」全枚举出来又是指数级，算不动。

破局的观察是：站在第 i 家门口，无论前面怎么选，当下只有两种决策——偷这家，或不偷这家。而这两种决策的收益，都只取决于「前面几家的最优结果」，不取决于前面具体偷了哪几家。子问题重叠又能复用，动态规划顺势而出。

dp 状态怎么定义，初值为什么这么设

定义 dp[i] 为「只考虑前 i+1 家（下标 0 到 i）时能偷到的最大金额」，注意它的含义是最优值，不承诺第 i 家一定被偷。初值铺两个：dp[0] = nums[0]，只有一家当然直接偷；dp[1] = max(nums[0], nums[1])，前两家相邻只能选一家，挑大的。dp[1] 容易被顺手写成 nums[1]，那就漏了第 0 家更有钱的情形。

偷与不偷的转移方程为什么成立

对第 i 家做二选一：不偷，那么前 i+1 家的最优就是前 i 家的最优，直接沿用 dp[i-1]；偷，则第 i-1 家必须放弃，收益是 dp[i-2] + nums[i]。第 i 家的所有选法必然落入这两类之一，所以 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 覆盖了全部可能，取大即最优。

这一步能成立还依赖一个隐含性质：一旦决定第 i 家偷不偷，前面子问题的最优解不会因为这个决定而失效——这就是无后效性，白话说就是「过去的最优怎么来的不重要，值对就行」。

复杂度怎么算，答案取哪一项

每家只做一次比较和一次加法，扫一遍数组即可，时间 O(n)；dp[i] 只依赖前两项，用两个滚动变量轮替就够，空间 O(1)，参考代码里 a, b = b, max(b, a + x) 一行完成。

两个易翻车点：一是答案取 dp[n-1] 而不是「最后一家偷的那条路」，因为最后一家完全可能不偷；二是姊妹题 LeetCode 213 把街道改成环形、首尾相邻，做法是拆成「不偷第一家」和「不偷最后一家」两条线性 DP，取两者较大者。

Python

def rob(nums):
    a, b = 0, 0   # dp[i-2], dp[i-1]
    for x in nums:
        a, b = b, max(b, a + x)
    return b

C++

int rob(vector<int>& nums){
    int a = 0, b = 0;
    for(int x : nums){ int c = max(b, a + x); a = b; b = c; }
    return b;
}

Java

int rob(int[] nums){
    int a = 0, b = 0;
    for(int x : nums){ int c = Math.max(b, a + x); a = b; b = c; }
    return b;
}