House Robber

Concept

LeetCode #198.
Problem: 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.

Input: nums = [1, 2, 3, 1]
Output: 4 (Rob house 0 for $1, skip house 1, rob house 2 for$3. 1 + 3 = 4).

Input: nums = [2, 7, 9, 3, 1]
Output: 12 (Rob 2, 9, 1).

The DP Strategy

We are moving through the array left to right.
When we stand in front of House i, we have exactly two choices:

1. Rob it: If we rob House i, we CANNOT rob House i-1. The maximum profit would be the money in this house (nums[i]) PLUS the optimal maximum profit we had accumulated up to House i-2.
2. Skip it: If we skip House i, we gain $0 here. But it means the optimal maximum profit up to House i remains exactly the optimal maximum profit we had accumulated at House i-1.

We want to maximize our money, so we take the Math.max of these two choices!

Recurrence Relation:
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1])
(Rob Current + Max Profit from 2 houses ago) vs (Skip Current and keep Max Profit from 1 house ago).

Implementation (Tabulation)

// Time Complexity: O(N)
// Space Complexity: O(N)

function rob(nums: number[]): number {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    const dp = new Array(nums.length);

    // Base Cases
    // If there is only 1 house, the max profit is just robbing that 1 house.
    dp[0] = nums[0];
    
    // If there are 2 houses, you can only rob the larger of the two.
    dp[1] = Math.max(nums[0], nums[1]);

    // Build the DP table
    for (let i = 2; i < nums.length; i++) {
        // To Rob, or Not To Rob
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }

    return dp[nums.length - 1];
}

State Reduction ($O(1)$ Space)

Just like Climbing Stairs, dp[i] only physically looks back at dp[i-1] and dp[i-2]. We can perfectly optimize this to $O(1)$ space.

// Time Complexity: O(N)
// Space Complexity: O(1)

function robOptimized(nums: number[]): number {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let twoBack = nums[0]; // dp[0]
    let oneBack = Math.max(nums[0], nums[1]); // dp[1]

    for (let i = 2; i < nums.length; i++) {
        const currentMax = Math.max(nums[i] + twoBack, oneBack);
        
        // Slide the pointers!
        twoBack = oneBack;
        oneBack = currentMax;
    }

    return oneBack;
}

House Robber II (The Circle)

LeetCode #213. What if the houses are arranged in a Circle?
Because it’s a circle, the First House and the Last House are physically adjacent. You cannot rob both.

The Solution:
If you rob the First House, you are mathematically banned from the Last House. The problem is now an array from [0] to [length - 2].
If you rob the Last House, you are mathematically banned from the First House. The problem is now an array from [1] to [length - 1].

You literally just run the exact same robOptimized function twice:
return Math.max( robOptimized(nums.slice(0, n - 1)), robOptimized(nums.slice(1, n)) );

Interview Questions

Q: A developer suggests grabbing all the Evens (nums[0] + nums[2] + nums[4]) and all the Odds (nums[1] + nums[3]), and just returning the Math.max of the two sums. Does this work?
A: No, this is a fatal logic error.
Imagine nums = [2, 1, 1, 2].
Evens: 2 + 1 = 3.
Odds: 1 + 2 = 3.
The DP algorithm: Rob index 0 (2), skip index 1, skip index 2, rob index 3 (2). Total: 2 + 2 = 4.
The Evens/Odds approach falsely assumes you MUST strictly alternate every single house. But skipping TWO houses in a row is perfectly legal and often optimal!