How can I solve the House Robber II problem efficiently?

The solution requires breaking the problem into two subarrays, excluding either the first or the last house, and applying dynamic programming to each subarray.

Why can't I rob both the first and last house in House Robber II?

Since the houses are arranged in a circle, the first and last houses are adjacent. Robbing both would trigger the security system, so they must be considered separately.

What is the time complexity of the optimal solution for House Robber II?

The optimal solution has a time complexity of O(n), as we make two passes over the array to solve each subproblem.

What type of dynamic programming is used in House Robber II?

This problem uses state transition dynamic programming to decide at each house whether to rob it or skip it.

Can you optimize the space complexity for House Robber II?

Yes, by storing only the previous two results in dynamic programming, the space complexity can be reduced to O(1).

#213

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在…

数组动态规划

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

lightbulb

解题思路

方法一：动态规划

环状排列意味着第一个房屋和最后一个房屋中最多只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房屋子问题。

时间复杂度 $O(n)$ ，其中 $n$ 是数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def rob(self, nums: List[int]) -> int:
        def _rob(nums):
            f = g = 0
            for x in nums:
                f, g = max(f, g), f + x
            return max(f, g)

        if len(nums) == 1:
            return nums[0]
        return max(_rob(nums[1:]), _rob(nums[:-1]))

speed

复杂度分析

指标	值
时间	complexity is O(n) due to the two passes over the array to compute the maximum loot for each subproblem. Space complexity is O(1) if we use optimized space for dynamic programming, or O(n) if we store results for each house.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate identifies the need to handle the circular nature of the problem.
question_mark
They break the problem into two linear subproblems, using dynamic programming in each case.
question_mark
The candidate demonstrates the ability to optimize space usage in dynamic programming solutions.

warning

常见陷阱

外企场景

error
Failing to account for the circular nature of the problem, leading to incorrect assumptions about which houses can be robbed together.
error
Not optimizing space usage in dynamic programming, leading to unnecessary memory consumption.
error
Misunderstanding the subproblem breakdown and incorrectly applying dynamic programming to the entire array without separating the two cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple rounds of robbery, where you can rob houses again after a set number of nights.
arrow_right_alt
Adding additional constraints, such as limits on the number of houses you can rob in one go.
arrow_right_alt
Robbing houses with variable amounts of money that change each night.

help

常见问题

外企场景

继续练习

#221 最大正方形 #198 打家劫舍 #188 买卖股票的最佳时机 IV