House Robber V - Solution & Explanation

Problem Overview: You are given an array where each element represents money in a house. Robbing two adjacent houses triggers the alarm, so you must choose houses such that no two selected indices are neighbors while maximizing the total amount stolen.

Approach 1: Brute Force Recursion (O(2^n) time, O(n) space)

Start from the first house and recursively decide whether to rob it or skip it. If you rob house i, the next valid choice is i + 2; if you skip it, move to i + 1. The recursion explores every valid subset of houses and returns the maximum sum. This approach clearly models the decision process but recomputes the same subproblems many times, causing exponential time complexity. The recursion stack requires O(n) space in the worst case.

Approach 2: Top-Down Dynamic Programming (Memoization) (O(n) time, O(n) space)

Use memoization to cache results for each index. Define dp[i] as the maximum amount you can steal starting from house i. During recursion, check if the value is already computed; if so, reuse it instead of recalculating. Each index is evaluated once, turning the exponential recursion into a linear-time solution. This pattern is a classic example of dynamic programming where overlapping subproblems are stored and reused.

Approach 3: Bottom-Up Dynamic Programming (O(n) time, O(n) space)

Instead of recursion, build the solution iteratively. Let dp[i] represent the maximum amount that can be robbed considering houses up to index i. For each house, choose between skipping it (dp[i-1]) or robbing it (nums[i] + dp[i-2]). The transition becomes dp[i] = max(dp[i-1], nums[i] + dp[i-2]). This approach avoids recursion overhead and makes the state transition explicit. It works naturally with the linear structure of the array.

Approach 4: Space-Optimized Dynamic Programming (O(n) time, O(1) space)

The DP state only depends on the previous two values, so storing the entire array is unnecessary. Track two variables: prev1 for the best result up to the previous house and prev2 for the result two houses back. For each value, compute the new maximum using max(prev1, prev2 + value), then shift the variables forward. This reduces memory usage to constant space while preserving linear time. It is the most common implementation for interview solutions involving dynamic programming transitions on sequential data.

Recommended for interviews: The space‑optimized dynamic programming solution is typically expected. Interviewers want to see that you first recognize the overlapping subproblem structure, derive the recurrence max(skip, rob), and then reduce the state to constant space. Discussing the brute force recursion briefly shows you understand the decision tree, but implementing the optimized DP demonstrates strong problem‑solving and optimization skills.