198. House Robber

Time: O(n)

Space: O(n)

Intuition

At each house you have two choices: rob it (and skip the previous) or skip it (and keep whatever was best through the previous house). This gives the recurrence dp[i] = max(dp[i-2] + nums[i], dp[i-1]). Only the last two dp values are ever needed, so the array collapses to two variables.

Algorithm

1If n == 1, return nums[0].
2Initialise prev2 = nums[0] (best loot through house 0), prev1 = max(nums[0], nums[1]) (best through house 1).
3For i from 2 to n-1: cur = max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = cur.
4Return prev1.

Example Walkthrough

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

1.prev2=2, prev1=max(2,7)=7.
2.i=2 (nums=9): cur=max(7, 2+9)=11. prev2=7, prev1=11.
3.i=3 (nums=3): cur=max(11, 7+3)=11. prev2=11, prev1=11.
4.i=4 (nums=1): cur=max(11, 11+1)=12. prev2=11, prev1=12.

Output: 12 (rob houses 0,2,4: 2+9+1=12)

Common Pitfalls

•Initialise prev1 = max(nums[0], nums[1]) not just nums[1] - you might not rob house 1.
•Do not reset dp to 0 at any step - you always carry forward the best previous answer.

198.cs

// Approach: Top-down DP with memoization.
// At each house i, the best loot is max(rob[i-2] + nums[i], rob[i-1]):
// either rob this house (gaining nums[i] plus best loot two houses back)
// or skip it (keeping the best loot from the previous house).
// Memoization ensures each sub-problem is solved only once, giving O(n) time.
// Time: O(n) Space: O(n)

public class Solution
{
    public int Rob(int[] nums)
    {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, -1);

        return topDown(n - 1, nums, dp);
    }

    private int topDown(int ind, int[] nums, int[] dp)
    {
        if (ind < 0)
            return 0;

        if (dp[ind] != -1)
            return dp[ind];

        int take = nums[ind] + topDown(ind - 2, nums, dp);
        int notTake = topDown(ind - 1, nums, dp);

        return dp[ind] = Math.Max(take, notTake);
    }
}

Was this solution helpful?