198. House Robber Medium

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: 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
Explanation: 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.

Approach

Input: An array nums representing the amount of money in each house.

Output: Return the maximum amount of money that can be robbed under the condition of not robbing adjacent houses.

This problem belongs to Linear DP problems.

1. Abstracting the problem into Dynamic Programming

This is a problem where "optimal solutions of subproblems constitute the global optimal solution", matching the characteristics of dynamic programming:

• If you rob the i-th house, you cannot rob the i-1-th house;
• If you do not rob the i-th house, you can inherit the optimal solution from i-1.

2. State Definition

Let f[i] denote the maximum amount of money that can be robbed from the first i houses (0-indexed).

3. State Transition Equation

For each house i, there are two choices:

• Do not rob the i-th house: The maximum profit is f[i-1].
• Rob the i-th house: The maximum profit is f[i-2] + nums[i].

So:

f[i] = max(f[i - 1], f[i - 2] + nums[i])

4. Initial Conditions

f[0] = nums[0]                   # Only one house, can only rob it
f[1] = max(nums[0], nums[1])     # Two houses, rob the one with larger amount

5. Target Value

The final answer is f[n - 1], which is the maximum amount that can be obtained after considering all houses.

Implementation

Rolling Array Approach

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Initialize two states:
        # f0 represents the maximum profit if we do NOT rob the current house
        # f1 represents the maximum profit if we rob the current house (new calculation)
        f0, f1 = 0, 0

        for num in nums:
            # Max profit for current = max(previous not robbed + current value, previous robbed)
            # Not robbing current house = larger of previously robbed or not robbed (which resolves to f1)
            new_f = max(f0 + num, f1)
            f0 = f1
            f1 = new_f
        
        return f1

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    let f0 = 0;
    let f1 = 0;

    for (let x of nums) {
        const newF = Math.max(f0 + x, f1);
        f0 = f1;
        f1 = newF;
    }

    return f1;
};

Memoized Recursion Approach

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Forward robbing
        n = len(nums)
        # Cache for already calculated answers
        cache = [-1] * n
        def dfs(i):
            # No more houses if index passes the last one
            if i >= n:
                return 0
            # Return cached answer directly if calculated before
            if cache[i] != -1:
                return cache[i]
            # Robbing house i means finding max among remaining houses from i + 2
            # Skipping house i means finding max among remaining houses from i + 1
            res = max(dfs(i + 1), dfs(i + 2) + nums[i])
            # Cache the current calculated result
            cache[i] = res
            return res
        return dfs(0)

        # Backward robbing
        n = len(nums)
        cache = [-1] * n
        def dfs(i):
            # Recursion base case
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
            # Robbing house i means finding max up to i - 2
            # Skipping house i means finding max up to i - 1
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            cache[i] = res
            return res
        # Start robbing from the last house
        return dfs(n - 1)

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // Forward robbing
    const cache = {};
    function dfs(i) {
        if (i >= nums.length) return 0;

        if (cache[i] != null) return cache[i];

        const res = Math.max(dfs(i + 1), dfs(i + 2) + nums[i]);

        cache[i] = res;

        return res;
    }

    return dfs(0); 
    
    // Backward robbing
    /*
    const cache = {};
    function dfs(i) {
        if (i < 0) return 0;

        if (cache[i] != null) return cache[i];

        const res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);

        cache[i] = res;

        return res;
    }

    return dfs(nums.length - 1);
    */
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity:
  • Rolling Array Approach: O(1)
  • Memoized Recursion Approach: O(n)

Links

198. House Robber (English)

198. 打家劫舍 (Chinese)