Dynamic Programming

1D Dynamic Programming: Breaking Down the House Robber

May 2026
9 min read

Dynamic Programming (DP) is the most feared algorithmic topic. But at its core, DP is just recursion with an excellent memory. Let's demystify it using the classic House Robber problem.

Introduction

In the classic House Robber problem (LeetCode #198), you are a thief planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing every single house is that adjacent houses have connected security systems. If you rob two houses side-by-side, the police will be called.

You need to figure out the maximum amount of money you can rob tonight without triggering the alarms.

The Core Logic (The Recurrence Relation)

If we are standing at house i, we have exactly two choices:

  1. Skip this house: We don't rob it. The total money we have is whatever the maximum was at the previous house (house[i-1]).
  2. Rob this house: We take the money here, but it means we couldn't have robbed the house directly next door. Our total is the money at this house plus whatever the maximum was two houses ago (house[i-2]).

The optimal choice is simply whichever of those two numbers is bigger.

dp[i] = Math.max( dp[i-1], dp[i-2] + currentHouseValue )

Step 1: Tabulation (O(N) Space)

The easiest way to solve this is to create a dp array of the exact same size as the street, and fill it out sequentially from left to right.

java
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);

for(int i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.length - 1];

This works perfectly, but creating a whole new array costs $O(N)$ extra memory.

Step 2: Space Optimization (O(1) Space)

Look closely at our formula: dp[i] = Math.max( dp[i-1], dp[i-2] + nums[i] ).

To calculate the maximum money at our current house, we only ever look back exactly two steps. We don't care about what happened at house i-3, i-4, or i-10.

Because we only need the two previous states, storing the entire array is a waste of memory. We can replace the array with two simple integer variables: prev1 (representing dp[i-1]) and prev2 (representing dp[i-2]).

As we loop through the houses, we calculate the current max, and then simply shift our variables forward to prepare for the next loop.

Final Thoughts

This evolution—from a recursive thought process, to an $O(N)$ array (Tabulation), down to $O(1)$ variables (Space Optimization)—is the exact lifecycle of mastering Dynamic Programming. Always start by finding the relation, map it to an array, and then see if you can compress the required memory!

Implementation

java
class Solution { public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int prev2 = 0; // Represents dp[i-2] int prev1 = 0; // Represents dp[i-1] for (int num : nums) { int current = Math.max(prev1, prev2 + num); // Shift the window forward prev2 = prev1; prev1 = current; } return prev1; } }