House Robber: A First-Principles Journey Through Dynamic Programming

A deep dive into the thinking process behind Dynamic Programming, inspired by Richard Bellman's original insights

Part 1: The Designer's Brain - Before Any Code

The Raw Problem

You're a robber on a street with houses [2, 7, 9, 3, 1]. Each number is money in that house.

Constraint: Rob two adjacent houses → alarm triggers.

Question: What's the maximum money you can steal?

First Instinct (The Greedy Trap)

Designer's first thought: "Just take the biggest houses!"

Pick 9 (index 2)
Can't take 7 or 3 (adjacent)
Take 2 and 1
Total: 9 + 2 + 1 = 12

But wait... what if we took 7 + 9 + 1 = 17? That's better!

KEY REALIZATION #1

Greedy doesn't work because local optimal ≠ global optimal

The "best choice right now" might block better choices later.

The Recursive Insight (Designer's Second Attempt)

Designer thinks: "At each house, I have a CHOICE..."

Standing at house i, I can:

Rob it → get money[i] + whatever I got from house i-2 onwards (can't touch i-1)
Skip it → get whatever I got from house i-1 onwards

In math:

max_money(i) = max(
    money[i] + max_money(i-2),  // rob this house
    max_money(i-1)               // skip this house
)

Let's trace this on `[2, 7, 9, 3, 1]`:

max_money(4) = max(
    1 + max_money(2),
    max_money(3)
)

But to know max_money(3), we need:

max_money(3) = max(
    3 + max_money(1),
    max_money(2)
)

To know max_money(2), we need:

max_money(2) = max(
    9 + max_money(0),
    max_money(1)
)

...and so on

KEY REALIZATION #2

This breaks down into OVERLAPPING SUBPROBLEMS

Part 2: Bellman's Brain - The Birth of Dynamic Programming

The Historical Context

Bellman wasn't thinking about house robbers. He was working on multi-stage decision processes for the RAND Corporation (military planning). Think:

"How do I allocate resources across multiple time periods to maximize overall outcome?"

Similar structure:

At each time period (like each house), make a decision
Each decision affects future options
Want to maximize total value

Bellman's Core Insight: "Optimal Substructure"

The Principle of Optimality (Bellman's exact words, 1957):

"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision."

Translation to human:

If you know the optimal solution from position i, and you want the optimal solution from position i+1, you don't need to reconsider everything before position i.

The best path to the end from i+1 can be built using the best path from i.

Let's Break This Down With House Robber

Question: What's the max money from house 0 to house 4?

Bellman's approach:

If I knew the max money from houses 0→3, and
If I knew the max money from houses 0→2,
Then I could instantly compute max from 0→4:

max(0→4) = max(
    money[4] + max(0→2),  // rob house 4
    max(0→3)               // skip house 4
)

KEY REALIZATION #3

The solution to a problem can be constructed from solutions to smaller subproblems

This is optimal substructure.

But Why Is This Revolutionary?

The naive recursive approach recalculates the same subproblems exponentially many times:

                    rob(4)
                   /      \
              rob(3)      rob(2)
              /    \      /     \
         rob(2)  rob(1) rob(1) rob(0)
         /   \    /  \    /  \
    rob(1) rob(0) ...  ...  ...

See how rob(2) appears multiple times? And rob(1)?

For array size n, this branches exponentially: O(2^n) calls!

Bellman's Leap: "Just Remember What You Calculated"

The insight: If rob(2) is being calculated multiple times, and it always gives the same answer, why recalculate?

Store it.

This is memoization - the "memo" in DP.

memo = {}

def rob(i):
    if i in memo:
        return memo[i]  # Already solved this!

    # Calculate and store
    memo[i] = max(money[i] + rob(i-2), rob(i-1))
    return memo[i]

Now each subproblem is solved exactly once.

Time complexity drops from O(2^n) to O(n).

Part 3: The Bottom-Up Revelation (True DP)

Designer realizes: "If I'm going to solve all subproblems anyway, why use recursion? Why not solve them in ORDER?"

The Bottom-Up Approach

houses = [2, 7, 9, 3, 1]

# Start small:
dp[0] = 2           # only house 0, rob it
dp[1] = max(2, 7) = 7   # either house 0 or 1

# Build up:
dp[2] = max(9+dp[0], dp[1]) = max(9+2, 7) = 11
dp[3] = max(3+dp[1], dp[2]) = max(3+7, 11) = 11
dp[4] = max(1+dp[2], dp[3]) = max(1+11, 11) = 12

KEY REALIZATION #4

You can solve subproblems in a specific order (usually smallest to largest) and build up to the answer

This is tabulation - the table-based DP.

Part 4: The Meta-Process - How to Think in DP

Bellman's Mental Checklist (The Engineering Framework)

Step 1: Can this be broken into decisions at stages?

House robber: At each house, decide rob/skip
Fibonacci: At each position, it's sum of previous two
Knapsack: At each item, decide include/exclude

Step 2: Does each decision affect future options?

House robber: Robbing house i means can't rob i+1
Stock prices: Buying stock means can't buy again until sell

Step 3: Can you write the solution as a recurrence relation?

f(i) = some_function(f(i-1), f(i-2), ..., current_choice)

Step 4: Are subproblems reused?

If yes → DP is worth it
If no → regular recursion is fine

Step 5: What's the order of dependencies?

House robber: dp[i] depends on dp[i-1] and dp[i-2]
So solve left to right

Part 5: Why "Dynamic Programming"? (The Name's Origin)

Fun Fact

Bellman chose the name to impress his bosses who didn't like mathematics.

His own words:

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name... I wanted to get across the idea that this was dynamic... multistage... I thought dynamic programming was a good name. It was something not even a Congressman could object to."

The word "programming" here means "planning" (like a military program), not coding!

"Dynamic" refers to the time-varying aspect (multi-stage decisions).

Part 6: Edge Cases as Concept Validators

Let's test your understanding:

Edge Case 1: `[5]` (one house)

What should happen? Rob it, get 5

Does DP handle this? Yes, base case: dp[0] = houses[0] ✅

Edge Case 2: `[5, 1]` (two houses)

What should happen? Rob house 0, get 5

Does DP handle this? dp[1] = max(5, 1) = 5 ✅

Edge Case 3: `[5, 10, 5]`

Naive thinking: Rob middle (10)

Correct: Rob first + last (5+5=10)

DP: dp[2] = max(5+5, 10) = 10 ✅

Why it works: The recurrence automatically considers both options

Edge Case 4: `[2, 1, 1, 2]`

Greedy fails: Takes 2, then 2 = 4

Optimal: 2 + 1 + 2 = 5 (skip house 1, rob 0,2,3)

Wait, can you rob house 0 and 3? YES! They're not adjacent

DP finds this: dp[3] = max(2+dp[1], dp[2]) explores this path ✅

Part 7: The Three Approaches Clarified

Student's Critical Question

You mentioned three things here: one recursion, one dp, and one dp with memo... but I only see two things: recursion and dp with memo. Where is only dp or is there a only dp here at all?

This is a brilliant catch! Let me clarify the three distinct approaches:

1. PURE RECURSION (Top-Down, No Memory)

def rob(houses, i):
    # Base cases
    if i < 0:
        return 0
    if i == 0:
        return houses[0]

    # Recurrence relation - but RECALCULATES everything
    return max(
        houses[i] + rob(houses, i-2),  # rob this house
        rob(houses, i-1)                # skip this house
    )

# Call it
result = rob([2, 7, 9, 3, 1], 4)

Characteristics:

Starts from the END (house 4) and works backward
Recalculates the same subproblems multiple times
Time complexity: O(2^n)
This is NOT DP - it's just recursion

2. MEMOIZATION (Top-Down DP)

def rob_memo(houses, i, memo):
    # Base cases
    if i < 0:
        return 0
    if i == 0:
        return houses[0]

    # Check if already calculated
    if i in memo:
        return memo[i]

    # Calculate and STORE
    memo[i] = max(
        houses[i] + rob_memo(houses, i-2, memo),
        rob_memo(houses, i-1, memo)
    )
    return memo[i]

# Call it
memo = {}
result = rob_memo([2, 7, 9, 3, 1], 4, memo)

Characteristics:

Still recursive (top-down)
But now REMEMBERS what it calculated
Time complexity: O(n)
This IS DP - specifically "top-down DP"

3. TABULATION (Bottom-Up DP) - The "Pure DP"

def rob_tabulation(houses):
    if len(houses) == 0:
        return 0
    if len(houses) == 1:
        return houses[0]

    # Create a table
    dp = [0] * len(houses)

    # Base cases
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])

    # Fill table from BOTTOM to TOP (left to right)
    for i in range(2, len(houses)):
        dp[i] = max(
            houses[i] + dp[i-2],  # rob this house
            dp[i-1]                # skip this house
        )

    return dp[-1]

# Call it
result = rob_tabulation([2, 7, 9, 3, 1])

Characteristics:

NO recursion at all - just a loop
Starts from the BEGINNING (house 0) and works forward
Fills a table systematically
Time complexity: O(n)
This IS DP - specifically "bottom-up DP"

The Key Distinction

Is memoization the same as DP?

Technically: Memoization is a technique that can turn recursion into DP.
Bellman's original DP: He actually described the bottom-up tabulation approach. This is the "classic" DP.
Later: People realized you could achieve the same effect with recursion + memoization.

So There Are Really TWO Flavors of DP:

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Direction	Start from final answer, recurse to base	Start from base cases, build to final answer
Implementation	Recursive function + cache	Iterative loop + table
When to use	When recursion feels natural, or subproblems are sparse	When you need to solve ALL subproblems anyway
Bellman's original	❌ Not what he described	✅ This is "classic DP"

Let's Trace Both on `[2, 7, 9, 3, 1]`:

Top-Down (Memoization):

Call rob(4)
  → Need rob(3) and rob(2)
  → rob(3) needs rob(2) and rob(1)
  → rob(2) needs rob(1) and rob(0)
  → rob(1) needs rob(0) and rob(-1)
  → rob(0) = 2 (base case)
  → rob(-1) = 0 (base case)
  → rob(1) = max(7 + 0, 2) = 7 [STORE in memo]
  → rob(2) = max(9 + 2, 7) = 11 [STORE in memo]
  → rob(3) = max(3 + 7, 11) = 11 [STORE in memo]
  → rob(4) = max(1 + 11, 11) = 12

Execution order: rob(0) → rob(1) → rob(2) → rob(3) → rob(4)

(Even though we CALLED rob(4) first!)

Bottom-Up (Tabulation):

dp[0] = 2
dp[1] = max(2, 7) = 7
dp[2] = max(9 + dp[0], dp[1]) = max(11, 7) = 11
dp[3] = max(3 + dp[1], dp[2]) = max(10, 11) = 11
dp[4] = max(1 + dp[2], dp[3]) = max(12, 11) = 12

Execution order: dp[0] → dp[1] → dp[2] → dp[3] → dp[4]

(Explicitly left to right)

The Deep Question: Are They Really Different?

Philosophically: No. Both are solving the same subproblems in roughly the same order.

Practically: Yes.

When Memoization Shines:

# Imagine we only need rob(100) for a 1000-house array
# but the recurrence only needs rob(98), rob(96), rob(94)...
# Memoization: Only computes ~50 subproblems
# Tabulation: Computes all 1000 subproblems

When Tabulation Shines:

# When you KNOW you need all subproblems
# Tabulation is usually faster (no function call overhead)
# And uses less memory (no call stack)

Back to Bellman's Brain

When Bellman formulated DP in the 1950s, he described it as:

Define stages (houses 0, 1, 2, ...)
Define states at each stage (max money up to that house)
Write a recurrence relation (the max formula)
Build a table systematically (fill from stage 0 to stage n)

He didn't use recursion because computers in 1950 had tiny call stacks!

Memoization came later when recursion became more practical.

So, To Answer the Question Directly:

Question: "I only see two things: recursion and dp with memo. Where is the only DP?"

Answer: The "only DP" is the bottom-up tabulation approach (the for-loop version). That's what Bellman originally called "Dynamic Programming."

Memoization is a modern way to achieve the same result using recursion.

Both are valid DP, but if you're studying Bellman's original insight, focus on the bottom-up tabulation - that's the pure form.

Part 8: Java Implementation - Step by Step

Student's Request

Rewrite this like:
a = houses[i] + rob(houses, i-2)
b = rob(houses, i-1)
return max(a,b)
and in Java. This is more basic to me and more comprehensible.

Pure Recursion in Java

public int rob(int[] houses, int i) {
    // Base cases
    if (i < 0) {
        return 0;
    }
    if (i == 0) {
        return houses[0];
    }

    // Option 1: Rob this house + max from i-2
    int robCurrent = houses[i] + rob(houses, i - 2);

    // Option 2: Skip this house, take max from i-1
    int skipCurrent = rob(houses, i - 1);

    // Return the better option
    return Math.max(robCurrent, skipCurrent);
}

// How to call it:
// int result = rob(houses, houses.length - 1);

Let's Trace This Step-by-Step on `[2, 7, 9, 3, 1]`

Call: rob(houses, 4)

i = 4
robCurrent = houses[4] + rob(houses, 2)  // 1 + rob(houses, 2)
                                          // Need to calculate rob(houses, 2) first!
skipCurrent = rob(houses, 3)              // Need to calculate rob(houses, 3) first!

Now we go deeper: rob(houses, 3)

i = 3
robCurrent = houses[3] + rob(houses, 1)  // 3 + rob(houses, 1)
skipCurrent = rob(houses, 2)              // rob(houses, 2)

Even deeper: rob(houses, 2)

i = 2
robCurrent = houses[2] + rob(houses, 0)  // 9 + rob(houses, 0)
skipCurrent = rob(houses, 1)              // rob(houses, 1)

Keep going: rob(houses, 1)

i = 1
robCurrent = houses[1] + rob(houses, -1)  // 7 + rob(houses, -1)
skipCurrent = rob(houses, 0)               // rob(houses, 0)

Base case 1: rob(houses, 0)

i = 0
return houses[0]  // return 2

Base case 2: rob(houses, -1)

i = -1
return 0

Now Let's Unwind Back Up

At rob(houses, 1):

robCurrent = 7 + 0 = 7
skipCurrent = 2
return Math.max(7, 2) = 7

At rob(houses, 2):

robCurrent = 9 + 2 = 11
skipCurrent = 7
return Math.max(11, 7) = 11

At rob(houses, 3):

robCurrent = 3 + 7 = 10
skipCurrent = 11
return Math.max(10, 11) = 11

At rob(houses, 4):

robCurrent = 1 + 11 = 12
skipCurrent = 11
return Math.max(12, 11) = 12

Final answer: 12

The Problem: See How Much Work We Repeat?

Look at this call tree:

rob(4)
├── rob(2) ──┐
│   ├── rob(0) = 2    |
│   └── rob(1)        |
│       ├── rob(-1) = 0  |
│       └── rob(0) = 2 ← CALCULATED AGAIN!
│                      |
└── rob(3)            |
    ├── rob(1) ←──────┘ CALCULATED AGAIN!
    │   ├── rob(-1) = 0
    │   └── rob(0) = 2 ← CALCULATED AGAIN!
    └── rob(2) ← CALCULATED AGAIN!
        ├── rob(0) = 2 ← CALCULATED AGAIN!
        └── rob(1) ← CALCULATED AGAIN!

rob(0) is calculated 5 times!
rob(1) is calculated 3 times!
rob(2) is calculated 2 times!

For houses.length = 30, you'd calculate rob(0) potentially millions of times!

Part 9: Memoization = Recursion + Memory

Student's Question

And is MEMOIZATION DP just recursion with memo?

Answer: YES! Exactly!

The Whole Concept

Memoization = Recursion + Memory

That's it. That's the whole concept.

Let's See It in Java

public int robWithMemo(int[] houses, int i, Map<Integer, Integer> memo) {
    // Base cases
    if (i < 0) {
        return 0;
    }
    if (i == 0) {
        return houses[0];
    }

    // CHECK: Have we already solved this?
    if (memo.containsKey(i)) {
        return memo.get(i);  // Just return it, don't recalculate!
    }

    // Option 1: Rob this house + max from i-2
    int robCurrent = houses[i] + robWithMemo(houses, i - 2, memo);

    // Option 2: Skip this house, take max from i-1
    int skipCurrent = robWithMemo(houses, i - 1, memo);

    // Calculate the result
    int result = Math.max(robCurrent, skipCurrent);

    // STORE it for future use
    memo.put(i, result);

    // Return it
    return result;
}

// How to call it:
// Map<Integer, Integer> memo = new HashMap<>();
// int result = robWithMemo(houses, houses.length - 1, memo);

The ONLY Difference from Pure Recursion

Pure Recursion:

public int rob(int[] houses, int i) {
    if (i < 0) return 0;
    if (i == 0) return houses[0];

    int robCurrent = houses[i] + rob(houses, i - 2);
    int skipCurrent = rob(houses, i - 1);
    return Math.max(robCurrent, skipCurrent);
}

Memoization (Recursion + Memo):

public int robWithMemo(int[] houses, int i, Map<Integer, Integer> memo) {
    if (i < 0) return 0;
    if (i == 0) return houses[0];

    if (memo.containsKey(i)) return memo.get(i);  // ← ADDED THIS

    int robCurrent = houses[i] + robWithMemo(houses, i - 2, memo);
    int skipCurrent = robWithMemo(houses, i - 1, memo);

    int result = Math.max(robCurrent, skipCurrent);
    memo.put(i, result);  // ← ADDED THIS

    return result;
}

Key Point

That's literally it. Two lines of code turn recursion into DP.

Let's Trace It on `[2, 7, 9, 3, 1]` with Memo

Initial state: memo = {}

Call: robWithMemo(houses, 4, memo)

i = 4
memo doesn't contain 4, so calculate:
robCurrent = houses[4] + robWithMemo(houses, 2, memo)  // Need rob(2)

Call: robWithMemo(houses, 2, memo)

i = 2
memo doesn't contain 2, so calculate:
robCurrent = houses[2] + robWithMemo(houses, 0, memo)  // Need rob(0)

Call: robWithMemo(houses, 0, memo)

i = 0
return houses[0] = 2  // Base case

Back to robWithMemo(houses, 2, memo):

robCurrent = 9 + 2 = 11
skipCurrent = robWithMemo(houses, 1, memo)  // Need rob(1)

Call: robWithMemo(houses, 1, memo)

i = 1
robCurrent = houses[1] + robWithMemo(houses, -1, memo) = 7 + 0 = 7
skipCurrent = robWithMemo(houses, 0, memo) = 2  // Already calculated, returns 2
result = Math.max(7, 2) = 7
memo.put(1, 7)  // memo = {1: 7}
return 7

Back to robWithMemo(houses, 2, memo):

robCurrent = 11
skipCurrent = 7
result = Math.max(11, 7) = 11
memo.put(2, 11)  // memo = {1: 7, 2: 11}
return 11

Back to robWithMemo(houses, 4, memo):

robCurrent = 1 + 11 = 12
skipCurrent = robWithMemo(houses, 3, memo)  // Need rob(3)

Call: robWithMemo(houses, 3, memo)

i = 3
robCurrent = houses[3] + robWithMemo(houses, 1, memo)
           = 3 + memo.get(1)  // ← LOOK! We already have this!
           = 3 + 7 = 10

skipCurrent = robWithMemo(houses, 2, memo)
            = memo.get(2)  // ← We already have this too!
            = 11

result = Math.max(10, 11) = 11
memo.put(3, 11)  // memo = {1: 7, 2: 11, 3: 11}
return 11

Finally back to robWithMemo(houses, 4, memo):

robCurrent = 12
skipCurrent = 11
result = Math.max(12, 11) = 12
memo.put(4, 12)  // memo = {1: 7, 2: 11, 3: 11, 4: 12}
return 12

Compare the Work Done

Pure Recursion:

rob(0) calculated: 5 times
rob(1) calculated: 3 times
rob(2) calculated: 2 times
rob(3) calculated: 1 time
rob(4) calculated: 1 time
Total function calls: 12

Memoization:

rob(0) calculated: 1 time (then reused)
rob(1) calculated: 1 time (then reused)
rob(2) calculated: 1 time (then reused)
rob(3) calculated: 1 time (then reused)
rob(4) calculated: 1 time
Total function calls: 5

The Key Insight

Understanding Memoization

Memoization DP = Take your recursive solution + add a cache (HashMap/Map) to remember results.

Bottom-up DP = Throw away recursion entirely, use a loop and a table instead.

Both achieve the same optimization. Both are "DP."

One More Thing to Solidify Understanding

The memo is doing EXACTLY what the dp table does in bottom-up DP.

In bottom-up, you explicitly create:

int[] dp = new int[houses.length];
dp[0] = houses[0];
dp[1] = Math.max(houses[0], houses[1]);
// ... fill the rest

In memoization, the Map<Integer, Integer> memo IS your dp table, just built on-demand instead of upfront.

Memoization is just "lazy DP" (only calculate what you need).

Conclusion: The Core Insight

What We've Learned

Dynamic Programming isn't magic - it's just recognizing that:

Problems can be broken into stages with choices
Each choice affects future options
Optimal solutions can be built from optimal subproblems
We keep recalculating the same things

Two ways to implement DP:

Top-down (Memoization): Recursion + cache
Bottom-up (Tabulation): Loop + table

Bellman's original insight was the bottom-up approach, but both are valid DP.

The meta-skill: Pattern recognition - when you see overlapping subproblems and optimal substructure, think DP.

The Prerequisite That Makes DP "Obvious"

What experienced engineers see instantly:

Problem has stages/positions
Each stage has choices
Choices affect future stages
Want optimal cumulative result
Same subproblems get recalculated ← This is the trigger

Pattern Recognition

Once you see these patterns, your brain automatically thinks: "This needs DP."

Complete Code Reference

// 1. Pure Recursion (Slow - O(2^n))
public int rob(int[] houses, int i) {
    if (i < 0) return 0;
    if (i == 0) return houses[0];

    int robCurrent = houses[i] + rob(houses, i - 2);
    int skipCurrent = rob(houses, i - 1);
    return Math.max(robCurrent, skipCurrent);
}

// 2. Top-Down DP (Memoization - O(n))
public int robMemo(int[] houses, int i, Map<Integer, Integer> memo) {
    if (i < 0) return 0;
    if (i == 0) return houses[0];
    if (memo.containsKey(i)) return memo.get(i);

    int robCurrent = houses[i] + robMemo(houses, i - 2, memo);
    int skipCurrent = robMemo(houses, i - 1, memo);
    int result = Math.max(robCurrent, skipCurrent);

    memo.put(i, result);
    return result;
}

// 3. Bottom-Up DP (Tabulation - O(n))
public int robDP(int[] houses) {
    if (houses.length == 0) return 0;
    if (houses.length == 1) return houses[0];

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

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

    return dp[houses.length - 1];
}

The Journey We Took

Started with greedy (failed)
Discovered recursive structure
Realized overlapping subproblems
Added memoization (top-down DP)
Converted to tabulation (bottom-up DP)
Understood Bellman's original thinking

This is the messy discovery journey - not the polished solution you find in textbooks.

Final Thought

The Core Philosophy

Dynamic Programming is not about memorizing patterns. It's about seeing the structure of decisions over time, recognizing when you're solving the same subproblems repeatedly, and being clever enough to remember the answers.

Once you internalize this way of thinking, DP problems stop being mysterious and start being obvious.

You now think like an engineer who understands DP from first principles. 🎯

Part 1: The Designer's Brain - Before Any Code​

The Raw Problem​

First Instinct (The Greedy Trap)​

The Recursive Insight (Designer's Second Attempt)​

Let's trace this on [2, 7, 9, 3, 1]:​

Part 2: Bellman's Brain - The Birth of Dynamic Programming​

The Historical Context​

Bellman's Core Insight: "Optimal Substructure"​

Let's Break This Down With House Robber​

But Why Is This Revolutionary?​

Bellman's Leap: "Just Remember What You Calculated"​

Part 3: The Bottom-Up Revelation (True DP)​

The Bottom-Up Approach​

Part 4: The Meta-Process - How to Think in DP​

Bellman's Mental Checklist (The Engineering Framework)​

Step 1: Can this be broken into decisions at stages?​

Step 2: Does each decision affect future options?​

Step 3: Can you write the solution as a recurrence relation?​

Step 4: Are subproblems reused?​

Step 5: What's the order of dependencies?​

Part 5: Why "Dynamic Programming"? (The Name's Origin)​

Part 6: Edge Cases as Concept Validators​

Edge Case 1: [5] (one house)​

Edge Case 2: [5, 1] (two houses)​

Edge Case 3: [5, 10, 5]​

Edge Case 4: [2, 1, 1, 2]​

Part 7: The Three Approaches Clarified​

Student's Critical Question​

1. PURE RECURSION (Top-Down, No Memory)​

2. MEMOIZATION (Top-Down DP)​

3. TABULATION (Bottom-Up DP) - The "Pure DP"​

The Key Distinction​

So There Are Really TWO Flavors of DP:​

Let's Trace Both on [2, 7, 9, 3, 1]:​

The Deep Question: Are They Really Different?​

Back to Bellman's Brain​

So, To Answer the Question Directly:​

Part 8: Java Implementation - Step by Step​

Student's Request​

Pure Recursion in Java​

Let's Trace This Step-by-Step on [2, 7, 9, 3, 1]​

Now Let's Unwind Back Up​

The Problem: See How Much Work We Repeat?​

Part 9: Memoization = Recursion + Memory​

Student's Question​

Let's See It in Java​

The ONLY Difference from Pure Recursion​

Let's Trace It on [2, 7, 9, 3, 1] with Memo​

Compare the Work Done​

The Key Insight​

One More Thing to Solidify Understanding​

Conclusion: The Core Insight​

What We've Learned​

The Prerequisite That Makes DP "Obvious"​

Complete Code Reference​

The Journey We Took​

Final Thought​

Part 1: The Designer's Brain - Before Any Code

The Raw Problem

First Instinct (The Greedy Trap)

The Recursive Insight (Designer's Second Attempt)

Let's trace this on `[2, 7, 9, 3, 1]`:

Part 2: Bellman's Brain - The Birth of Dynamic Programming

The Historical Context

Bellman's Core Insight: "Optimal Substructure"

Let's Break This Down With House Robber

But Why Is This Revolutionary?

Bellman's Leap: "Just Remember What You Calculated"

Part 3: The Bottom-Up Revelation (True DP)

The Bottom-Up Approach

Part 4: The Meta-Process - How to Think in DP

Bellman's Mental Checklist (The Engineering Framework)

Step 1: Can this be broken into decisions at stages?

Step 2: Does each decision affect future options?

Step 3: Can you write the solution as a recurrence relation?

Step 4: Are subproblems reused?

Step 5: What's the order of dependencies?

Part 5: Why "Dynamic Programming"? (The Name's Origin)

Part 6: Edge Cases as Concept Validators

Edge Case 1: `[5]` (one house)

Edge Case 2: `[5, 1]` (two houses)

Edge Case 3: `[5, 10, 5]`

Edge Case 4: `[2, 1, 1, 2]`

Part 7: The Three Approaches Clarified

Student's Critical Question

1. PURE RECURSION (Top-Down, No Memory)

2. MEMOIZATION (Top-Down DP)

3. TABULATION (Bottom-Up DP) - The "Pure DP"

The Key Distinction

So There Are Really TWO Flavors of DP:

Let's Trace Both on `[2, 7, 9, 3, 1]`:

The Deep Question: Are They Really Different?

Back to Bellman's Brain

So, To Answer the Question Directly:

Part 8: Java Implementation - Step by Step

Student's Request

Pure Recursion in Java

Let's Trace This Step-by-Step on `[2, 7, 9, 3, 1]`

Now Let's Unwind Back Up

The Problem: See How Much Work We Repeat?

Part 9: Memoization = Recursion + Memory

Student's Question

Let's See It in Java

The ONLY Difference from Pure Recursion

Let's Trace It on `[2, 7, 9, 3, 1]` with Memo

Compare the Work Done

The Key Insight

One More Thing to Solidify Understanding

Conclusion: The Core Insight

What We've Learned

The Prerequisite That Makes DP "Obvious"

Complete Code Reference

The Journey We Took

Final Thought