What is the optimal dynamic programming approach for solving House Robber?

The optimal dynamic programming approach uses state transitions to keep track of the maximum money robbed up to each house, either skipping the house or robbing it while maintaining a history of previous optimal solutions.

How do I reduce space complexity in the House Robber problem?

By using only two variables to store the last two results (representing the maximum robbed up to the previous house and the one before that), you can reduce the space complexity from O(n) to O(1).

What is the time complexity of the House Robber problem?

The time complexity of the House Robber problem is O(n), as we need to iterate through each house exactly once to calculate the maximum amount of money.

What should I be cautious about when solving the House Robber problem?

Be careful to correctly apply the state transition logic and avoid common pitfalls like failing to handle small arrays or overcomplicating the state transitions.

Can GhostInterview help me practice variations of the House Robber problem?

Yes, GhostInterview can generate variations of the problem, such as adding constraints like limiting the number of robberies or handling circular arrays, allowing you to practice and prepare for a range of interview scenarios.

#198

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 …

数组动态规划

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

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

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $\textit{dfs}(i)$ ，表示从第 $i$ 间房屋开始偷窃能够得到的最高金额。那么答案即为 $\textit{dfs}(0)$ 。

函数 $\textit{dfs}(i)$ 的执行过程如下：

如果 $i \ge \textit{len}(\textit{nums})$ ，表示所有房屋都被考虑过了，直接返回 $0$ ；
否则，考虑偷窃第 $i$ 间房屋，那么 $\textit{dfs}(i) = \textit{nums}[i] + \textit{dfs}(i+2)$ ；不偷窃第 $i$ 间房屋，那么 $\textit{dfs}(i) = \textit{dfs}(i+1)$ 。
返回 $\max(\textit{nums}[i] + \textit{dfs}(i+2), \textit{dfs}(i+1))$ 。

为了避免重复计算，我们使用记忆化搜索的方法，将 $\textit{dfs}(i)$ 的结果保存在一个数组或哈希表中，每次计算前先查询是否已经计算过，如果计算过直接返回结果。

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

1

2

3

4

5

6

7

8

9

10

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(nums):
                return 0
            return max(nums[i] + dfs(i + 2), dfs(i + 1))

        return dfs(0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of state transition dynamic programming and its application to linear problems.
question_mark
The candidate should be able to explain how dynamic programming optimizes the problem and how space can be minimized.
question_mark
Assess whether the candidate is able to apply iterative thinking and bottom-up approach to dynamic programming problems.

warning

常见陷阱

外企场景

error
Overcomplicating the solution by trying to include more than the last two houses in the dynamic programming calculation.
error
Failing to handle edge cases like small arrays (length 1 or 2) correctly.
error
Misunderstanding the state transitions, leading to incorrect logic for choosing whether to rob or skip a house.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Incorporating constraints such as a limited number of robberies (e.g., only robbing 'k' houses).
arrow_right_alt
Extending the problem to include circular arrays where the first and last houses are adjacent.
arrow_right_alt
Adjusting the problem to account for varying robbery costs or penalties for robbing certain houses.

help

常见问题

外企场景

继续练习

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