#198

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

House Robber

Maximize the amount of money you can rob tonight without alerting the police by applying dynamic programming with state transitions.

array dynamic programming

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, but there is a catch: adjacent houses have security systems, and triggering the alarm by robbing two adjacent houses will alert the police. Given an integer array 'nums' representing the amount of money in each house, your goal is to calculate the maximum amount of money you can rob tonight without alerting the police.

For example, consider nums = [1, 2, 3, 1]. Rob house 1 (money = 1), then rob house 3 (money = 3). The total amount you can rob is 4. However, robbing house 2 would set off the alarm due to proximity. Another example, nums = [2, 7, 9, 3, 1], allows robbing house 1, house 3, and house 5, totaling 12.

Examples

Example 1

Input: nums = [1,2,3,1]

Output: 4

Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example 2

Input: nums = [2,7,9,3,1]

Output: 12

Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Constraints

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

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to maintain a running total of the maximum money that can be robbed up to each house. At each house, you have two choices: either skip the house and carry forward the previous maximum or rob the house and add its value to the maximum from two houses prior (since adjacent houses can't be robbed).

Space Optimization

Rather than using an array to track the maximum amounts, you can optimize space by only keeping track of the last two results (the previous house and the house before that). This reduces the space complexity from O(n) to O(1).

Bottom-up Approach

Build the solution iteratively from the first house to the last, ensuring that at each step, you are choosing the optimal decision based on previously computed values. This avoids redundant calculations and ensures a time complexity of O(n).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to the single iteration through the houses to compute the maximum amount of money. The space complexity can be reduced to O(1) by storing only the last two computed results, though a more straightforward solution might use O(n) space to store all previous results.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Memoization Search

We design a function $\textit{dfs}(i)$, which represents the maximum amount of money that can be stolen starting from the $i$-th house. Thus, the answer is $\textit{dfs}(0)$.

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)

Solution 2: Dynamic Programming

We define $f[i]$ as the maximum total amount that can be robbed from the first $i$ houses, initially $f[0]=0$, $f[1]=nums[0]$.

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)

Solution 3: Dynamic Programming (Space Optimization)

We notice that when $i \gt 2$, $f[i]$ is only related to $f[i-1]$ and $f[i-2]$. Therefore, we can use two variables instead of an array to reduce the space complexity to $O(1)$.

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)

Continue Practicing

#188 best time to buy and sell stock iv #213 house robber ii #221 maximal square