打家劫舍 II 图解题解

打家劫舍 II 和 I 差在哪一句话

给一个数组 nums，每个值是一家现金，相邻两家不能同时偷，求最大总金额。和打家劫舍 I 唯一的区别：房子围成一圈，第一家和最后一家也相邻。就这句「首尾相邻」，原本离得最远的第一家和最后一家成了新邻居，直线题变成了环。

为什么直接套一遍线性 DP 会算错

打家劫舍 I 用线性 DP：DP 即动态规划，把算过的子问题存下来别重算；线性就是从头到尾扫一遍，靠递推（拿前面算好的值一步步推出后面的）往后推。它默认首尾两家离得远、互不影响。

环形里这个默认不成立：照直线跑一遍，dp 可能把下标 0 和 n-1 都选进最优，可它俩在环上是邻居，方案不合法。「首尾不能都偷」这条约束单条递推管不住。

为什么拆成两条直线取 max 就对了

麻烦全在首尾这对邻居上，就按它俩分情况。任何合法偷法，首尾至多占一家——至少有一端空着。两种情况合起来把所有合法方案兜住。

第一种把最后一家掐掉（只看 nums[0..n-2]），剩下是直线，第一家可偷；第二种把第一家掐掉（只看 nums[1..n-1]），最后一家可偷。每条上首尾不再相邻，就是打家劫舍 I，取更大那个。首尾都不偷的方案两条都算了，求 max 重复无妨，不漏就对。

每条直线里的 dp 怎么往前推

单条直线用 dp[i]=max(dp[i-1], dp[i-2]+nums[i])：不偷第 i 家就沿用前一家；偷第 i 家则前一家须空着，从 dp[i-2] 接过来加这家的钱。

参考代码用两个变量滚动：p 记 dp[i-2]、q 记 dp[i-1]，每步 p, q = q, max(q, p+x)，新 q 即当前最优。只留前两格，空间 O(1)。

手工演算：拿示例把两条直线都填出来

题面是环形数组 [2,3,9,4,1,8,6,2]，拆成两条直线：掐掉最后一家的 [2,3,9,4,1,8,6]、掐掉第一家的 [3,9,4,1,8,6,2]。第一条递推：dp[0]=2；dp[1]=max(2,3)=3；dp[2]=max(3,2+9)=11；dp[3]=max(11,3+4)=11；dp[4]=max(11,11+1)=12；dp[5]=max(12,11+8)=19；dp[6]=max(19,12+6)=19，结果 19。

第二条递推：dp[0]=3；dp[1]=max(3,9)=9；dp[2]=max(9,3+4)=9；dp[3]=max(9,9+1)=10；dp[4]=max(10,9+8)=17；dp[5]=max(17,10+6)=17；dp[6]=max(17,17+2)=19，结果 19。

环形答案 max(19,19)=19，对上题面输出。两条同分是巧合，取大的才是解。

复杂度多少，n=1 和空端两个边界

两条各扫一遍，每遍 O(n)、合起来仍 O(n)；每遍只留两个变量，空间 O(1)。

两处易错。一是区间切错：两条必须各漏一端、一条去尾一条去头，都留全就等于让首尾同时入选。二是 n==1：只有一家时去头去尾切完两条都空、各返回 0，会漏掉这家，得直接返回 nums[0]。

Python

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def line(a):
        p = q = 0
        for x in a: p, q = q, max(q, p + x)
        return q
    return max(line(nums[:-1]), line(nums[1:]))

C++

int line(vector<int>& v, int s, int e){
    int p = 0, q = 0;
    for(int i = s; i < e; i++){ int c = max(q, p + v[i]); p = q; q = c; }
    return q;
}
int rob(vector<int>& nums){
    int n = nums.size();
    if(n == 1) return nums[0];
    return max(line(nums, 0, n-1), line(nums, 1, n));
}

Java

int line(int[] v, int s, int e){
    int p = 0, q = 0;
    for(int i = s; i < e; i++){ int c = Math.max(q, p + v[i]); p = q; q = c; }
    return q;
}
int rob(int[] nums){
    int n = nums.length;
    if(n == 1) return nums[0];
    return Math.max(line(nums, 0, n-1), line(nums, 1, n));
}