LeetCode 213: House Robber II (Circular DP Split)

2026-03-26 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 213DPArrayInterview

Today we solve LeetCode 213 - House Robber II.

Source: https://leetcode.com/problems/house-robber-ii/

LeetCode 213 circular houses split into two linear DP ranges

English

Problem Summary

Each house has money, but adjacent houses cannot both be robbed. Unlike House Robber I, houses are arranged in a circle, so house 0 and house n-1 are also adjacent.

Key Insight

In a circle, you cannot rob both first and last house. So split into two linear subproblems and take max:

1) Rob from [0..n-2] (exclude last).
2) Rob from [1..n-1] (exclude first).

Brute Force and Limitations

Try all valid subsets with no adjacent picks. Correct but exponential, O(2^n), and impossible for interview constraints.

Optimal Algorithm Steps

For linear range, keep two states while scanning:
prev2 = best till i-2, prev1 = best till i-1.
Current best: cur = max(prev1, prev2 + nums[i]).
Then shift: prev2 = prev1, prev1 = cur.

Complexity Analysis

Time: O(n) (two linear passes).
Space: O(1).

Common Pitfalls

- Forgetting n == 1 special case.
- Running one linear DP on whole array (invalid for circle).
- Off-by-one when defining two ranges.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    private int robLinear(int[] nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    a := robLinear(nums, 0, n-2)
    b := robLinear(nums, 1, n-1)
    if a > b {
        return a
    }
    return b
}

func robLinear(nums []int, l, r int) int {
    prev2, prev1 := 0, 0
    for i := l; i <= r; i++ {
        cur := prev1
        if prev2+nums[i] > cur {
            cur = prev2 + nums[i]
        }
        prev2 = prev1
        prev1 = cur
    }
    return prev1
}

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    int robLinear(const vector& nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; ++i) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        return max(self.rob_linear(nums, 0, n - 2), self.rob_linear(nums, 1, n - 1))

    def rob_linear(self, nums: list[int], l: int, r: int) -> int:
        prev2 = prev1 = 0
        for i in range(l, r + 1):
            cur = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = cur
        return prev1

var rob = function(nums) {
  const n = nums.length;
  if (n === 1) return nums[0];
  return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
};

function robLinear(nums, l, r) {
  let prev2 = 0, prev1 = 0;
  for (let i = l; i <= r; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

中文

题目概述

每个房子有金额，不能偷相邻房子。与 House Robber I 不同的是本题房子首尾相连成环，所以 0 和 n-1 也相邻。

核心思路

因为首尾不能同时选，所以拆成两个线性子问题取最大值：
1）偷区间 [0..n-2]（排除最后一个）。
2）偷区间 [1..n-1]（排除第一个）。

暴力解法与不足

枚举所有不相邻子集可以得到正确结果，但复杂度 O(2^n)，输入稍大就不可用。

最优算法步骤

在线性区间上做滚动 DP：
prev2 表示到 i-2 的最优值，prev1 表示到 i-1 的最优值。
当前：cur = max(prev1, prev2 + nums[i])，然后状态右移。

复杂度分析

时间复杂度：O(n)（两次线性扫描）。
空间复杂度：O(1)。

常见陷阱

- 忽略 n == 1 的特判。
- 直接对整数组做一次线性 DP（会错误地允许首尾同取）。
- 区间端点写错导致漏算或越界。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    private int robLinear(int[] nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    a := robLinear(nums, 0, n-2)
    b := robLinear(nums, 1, n-1)
    if a > b {
        return a
    }
    return b
}

func robLinear(nums []int, l, r int) int {
    prev2, prev1 := 0, 0
    for i := l; i <= r; i++ {
        cur := prev1
        if prev2+nums[i] > cur {
            cur = prev2 + nums[i]
        }
        prev2 = prev1
        prev1 = cur
    }
    return prev1
}

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    int robLinear(const vector& nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; ++i) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        return max(self.rob_linear(nums, 0, n - 2), self.rob_linear(nums, 1, n - 1))

    def rob_linear(self, nums: list[int], l: int, r: int) -> int:
        prev2 = prev1 = 0
        for i in range(l, r + 1):
            cur = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = cur
        return prev1

var rob = function(nums) {
  const n = nums.length;
  if (n === 1) return nums[0];
  return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
};

function robLinear(nums, l, r) {
  let prev2 = 0, prev1 = 0;
  for (let i = l; i <= r; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}