The Three Approaches - Compact Reference

Problem: House Robber [2, 7, 9, 3, 1] - Maximum money without robbing adjacent houses

---

1. Pure Recursion (Slow - O(2^n))

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

    // Try both options
    int robCurrent = houses[i] + rob(houses, i - 2);
    int skipCurrent = rob(houses, i - 1);

    return Math.max(robCurrent, skipCurrent);
}

// Usage: rob(houses, houses.length - 1)

What happens:

• Solves same subproblems multiple times
• rob(0) calculated 5 times, rob(1) calculated 3 times
• Time: O(2^n) - exponential

Call tree:

rob(4)
├── rob(2)
│   ├── rob(0) ✓
│   └── rob(1)
│       ├── rob(-1)
│       └── rob(0) ✓ DUPLICATE!
└── rob(3)
    ├── rob(1) ✓ DUPLICATE!
    └── rob(2) ✓ DUPLICATE!

---

2. Top-Down DP (Memoization - O(n))

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

    // Check cache
    if (memo.containsKey(i)) return memo.get(i);

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

    // Store in cache
    memo.put(i, result);
    return result;
}

// Usage:
// Map<Integer, Integer> memo = new HashMap<>();
// robMemo(houses, houses.length - 1, memo)

What happens:

• Same recursion, but remembers results
• Each subproblem solved exactly once
• Time: O(n) - linear

Execution flow:

Call rob(4)
  → Calculate rob(0) = 2, store memo[0] = 2
  → Calculate rob(1) = 7, store memo[1] = 7
  → Calculate rob(2) = 11, store memo[2] = 11
  → Calculate rob(3) = 11, store memo[3] = 11
  → Calculate rob(4) = 12, store memo[4] = 12

memo = {0:2, 1:7, 2:11, 3:11, 4:12}

---

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];

    // Create table
    int[] dp = new int[houses.length];

    // Base cases
    dp[0] = houses[0];
    dp[1] = Math.max(houses[0], houses[1]);

    // Fill table left to right
    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];
}

// Usage: robDP(houses)

What happens:

• No recursion, just a loop
• Builds solution from smallest to largest
• Time: O(n) - linear

Execution flow:

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

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

dp = [2, 7, 11, 11, 12]
Answer: 12

---

Quick Comparison

Feature	Recursion	Memoization	Tabulation
Structure	Recursive	Recursive + cache	Loop + array
Direction	Top-down	Top-down	Bottom-up
Time	O(2^n)	O(n)	O(n)
Space	O(n) call stack	O(n) memo + stack	O(n) array only
When to use	Never (too slow)	Natural recursion	Faster, cleaner

---

The Only Difference

Recursion → Memoization:

// Add these 3 lines:
if (memo.containsKey(i)) return memo.get(i);  // Check cache
int result = ...;                              // Store calculation
memo.put(i, result);                           // Cache result

Memoization → Tabulation:

// Replace recursion with loop:
for (int i = 2; i < n; i++) {
    dp[i] = max(houses[i] + dp[i-2], dp[i-1]);
}

---

Mental Model

Recursion: "What do I need to solve this? Oh, I need those subproblems... let me calculate them... wait, I already calculated this before!"

Memoization: "What do I need? Let me check my notes first. Not there? OK, calculate and write it down."

Tabulation: "I'll solve all the small problems first in order, then use them to build bigger solutions."

---

Complete Working Example

public class HouseRobber {

    // 1. Pure Recursion
    public int robRecursive(int[] houses, int i) {
        if (i < 0) return 0;
        if (i == 0) return houses[0];
        return Math.max(
            houses[i] + robRecursive(houses, i - 2),
            robRecursive(houses, i - 1)
        );
    }

    // 2. Memoization
    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 result = Math.max(
            houses[i] + robMemo(houses, i - 2, memo),
            robMemo(houses, i - 1, memo)
        );
        memo.put(i, result);
        return result;
    }

    // 3. Tabulation
    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];
    }

    public static void main(String[] args) {
        HouseRobber hr = new HouseRobber();
        int[] houses = {2, 7, 9, 3, 1};

        // Method 1
        System.out.println(hr.robRecursive(houses, houses.length - 1)); // 12

        // Method 2
        Map<Integer, Integer> memo = new HashMap<>();
        System.out.println(hr.robMemo(houses, houses.length - 1, memo)); // 12

        // Method 3
        System.out.println(hr.robDP(houses)); // 12
    }
}