Master Dynamic Programming (DP): The 3 Core Approaches Explained with Fibonacci & House Robber

Dynamic Programming (DP) is a fundamental algorithmic optimization technique designed to solve complex computational problems by breaking them down into smaller subproblems, solving each unique subproblem exactly once, and storing their results in memory. By eliminating redundant recomputations inherent in naive recursion, DP dramatically improves runtime efficiency from exponential complexity to linear or polynomial time.

1. What is Dynamic Programming? (The Core Mental Model)

In plain recursion, an algorithm frequently solves the exact same subproblem multiple times. Dynamic Programming optimizes this process by retaining calculated results in a dedicated lookup structure (like an array or hash table). When the algorithm encounters a previously solved subproblem, it retrieves the precomputed answer instead of recalculating it.

                  Naive Recursion Problem
                  
                         solve(5)
                        /        \
                   solve(4)     solve(3)
                  /       \     /      \
             solve(3)   solve(2) solve(2) solve(1)
             
   Note: solve(3) and solve(2) are computed multiple times!

To apply Dynamic Programming, a problem must exhibit two crucial properties:

1. Overlapping Subproblems: The same subproblems are solved repeatedly throughout the recursive execution tree (e.g., computing $F(3)$ multiple times while calculating $F(5)$ in the Fibonacci sequence).
2. Optimal Substructure: The optimal solution to a larger problem can be constructed directly from the optimal solutions of its smaller subproblems.

2. The Three Core DP Paradigms

Dynamic Programming solutions are engineered using three distinct technical paradigms, spanning from intuitive recursive extensions to space-efficient iterative loops:

Synthesis Matrix of DP Approaches

3. Standardizing Paradigm #1: Top-Down DP (Memoization) via Fibonacci

The Top-Down approach directly models the mathematical definition of a recursive problem while maintaining a memory lookup table (cache) initialized to placeholder values (e.g., -1).

Mental Hook & Flow: Fibonacci $F(5)$

The standard Fibonacci mathematical formula is:

When executing top-down memoization, computation branches downward from $N=5$. When a calculated branch computes a value (e.g., $F(3) = 2$), it writes this value to the cache before returning. Subsequent branches reading $F(3)$ fetch it in $O(1)$ time.

Java Implementation: Fibonacci Top-Down (Memoization)

import java.util.Arrays;

public class FibonacciTopDown {
    public static int fibMemo(int n, int[] dp) {
        // Base Cases
        if (n == 0 || n == 1) {
            return n;
        }

        // Cache Hit: Return precomputed result
        if (dp[n] != -1) {
            return dp[n];
        }

        // Compute, Cache, and Return
        dp[n] = fibMemo(n - 1, dp) + fibMemo(n - 2, dp);
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1); // Initialize cache with -1
        
        System.out.println("Fibonacci(" + n + ") = " + fibMemo(n, dp));
    }
}

• Time Complexity: $O(N)$ — Every subproblem from $0$ to $N$ is evaluated exactly once.
• Space Complexity: $O(N)$ — $O(N)$ auxiliary array space for dp plus $O(N)$ explicit recursion stack depth.

4. Standardizing Paradigm #2: Bottom-Up DP (Tabulation) via Fibonacci

The Bottom-Up approach eliminates recursion completely. It constructs a tabular data structure (dp[]) sequentially, starting from the known smallest base cases ($0$ and $1$) and filling up to target $N$ iteratively using a for loop.

Linear Progression Flow

Java Implementation: Fibonacci Bottom-Up (Tabulation)

public class FibonacciBottomUp {
    public static int fibTabulation(int n) {
        if (n <= 1) return n;

        int[] dp = new int[n + 1];

        // Step 1: Initialize Base Cases
        dp[0] = 0;
        dp[1] = 1;

        // Step 2: Build table iteratively from base cases upward
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // Step 3: Return target result
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Fibonacci(" + n + ") = " + fibTabulation(n));
    }
}

• Time Complexity: $O(N)$ — Single iterative loop executing $N-1$ times.
• Space Complexity: $O(N)$ — Fixed-size 1D table array dp of length $N+1$. Call stack space is reduced to $O(1)$.

5. Standardizing Paradigm #3: Space Optimization via Fibonacci

Analyzing the recurrence formula $DP[i] = DP[i-1] + DP[i-2]$ reveals a structural pattern: computing the state at index $i$ requires only the preceding two calculated states ($i-1$ and $i-2$). Maintaining an entire array of size $N+1$ is redundant.

By swapping array slots for dynamic state variables (prev2 and prev1), memory consumption is reduced from linear to constant $O(1)$.

Variable Rotation Trace ($N=5$)

Initial State:
prev2 = 0  (represents F(0))
prev1 = 1  (represents F(1))

Loop Iteration i = 2:
   curr = prev1 + prev2  =>  1 + 0 = 1
   Shift States:
   prev2 = prev1         =>  1
   prev1 = curr          =>  1

Loop Iteration i = 3:
   curr = prev1 + prev2  =>  1 + 1 = 2
   Shift States:
   prev2 = prev1         =>  1
   prev1 = curr          =>  2

Loop Iteration i = 4:
   curr = prev1 + prev2  =>  2 + 1 = 3
   Shift States:
   prev2 = prev1         =>  2
   prev1 = curr          =>  3

Loop Iteration i = 5:
   curr = prev1 + prev2  =>  3 + 2 = 5
   Shift States:
   prev2 = prev1         =>  3
   prev1 = curr          =>  5

Final Return Value: prev1 (5)

Java Implementation: Fibonacci Space Optimized

public class FibonacciSpaceOptimized {
    public static int fibOptimized(int n) {
        if (n <= 1) return n;

        int prev2 = 0; // Represents F(i-2)
        int prev1 = 1; // Represents F(i-1)

        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Fibonacci(" + n + ") = " + fibOptimized(n));
    }
}

• Time Complexity: $O(N)$ — Single simple loop execution.
• Space Complexity: $O(1)$ — Extremely memory-efficient; uses only primitive integer variables.

6. Real-World Interview Problem: House Robber

LeetCode Problem Statement: You are a professional robber planning to rob houses along a street. Each house has a specific amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected — it will automatically contact the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police.

Structural Analysis & Recurrence Relation

When evaluating house index $i$, the robber faces a binary decision:

The fundamental DP Recurrence Relation becomes:

7. House Robber — Paradigm #1: Top-Down (Memoization)

Structural Execution Model (nums = [1, 2, 3, 1])

                          robFrom(0)
                        /            \
           ROB House 0 /              \ SKIP House 0
                      /                \
        1 + robFrom(2)                  robFrom(1)
          /        \                      /        \
   ROB 2 /          \ SKIP 2       ROB 1 /          \ SKIP 1
        /            \                  /            \
3 + robFrom(4)    robFrom(3)    2 + robFrom(3)    robFrom(2)
   [Base Case]   /          \      [Memoized!]    [Memoized!]
     = 0        ...        ...        = 1            = 3

Java Implementation: House Robber Top-Down

import java.util.Arrays;

public class HouseRobberTopDown {
    public static int robFrom(int i, int[] nums, int[] dp) {
        // Base Condition: Out of bounds
        if (i >= nums.length) {
            return 0;
        }

        // Cache Hit: Solution already evaluated
        if (dp[i] != -1) {
            return dp[i];
        }

        // Option 1: Rob current house i -> move to i + 2
        int rob = nums[i] + robFrom(i + 2, nums, dp);

        // Option 2: Skip current house i -> move to i + 1
        int skip = robFrom(i + 1, nums, dp);

        // Compute, Memoize, and Return
        dp[i] = Math.max(rob, skip);
        return dp[i];
    }

    public static int rob(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        return robFrom(0, nums, dp);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max Loot: " + rob(nums)); // Output: 4
    }
}

8. House Robber — Paradigm #2: Bottom-Up (Tabulation)

In bottom-up tabulation for House Robber, we solve subproblems backwards from the end of the array to index $0$.

Tabulation Formula & Base States

For an array of length $N$:

• Base State 1: $DP[N-1] = \text{nums}[N-1]$ (Only 1 house available to rob).
• Base State 2: $DP[N-2] = \max(\text{nums}[N-1], \text{nums}[N-2])$ (Choose the richer house between the last two).
• Iterative Loop: For index $i = N-3$ down to $0$:

Trace Walkthrough (nums = [1, 2, 3, 1], $N=4$)

Initialize DP Table of size N=4:
Base Case 1: DP[3] = nums[3] = 1
Base Case 2: DP[2] = Math.max(nums[3], nums[2]) = Math.max(1, 3) = 3

DP State Array so far: [ ? | ? | 3 | 1 ]

Loop Step i = 1:
   rob  = nums[1] + DP[3] = 2 + 1 = 3
   skip = DP[2]           = 3
   DP[1] = Math.max(3, 3) = 3
DP State Array so far: [ ? | 3 | 3 | 1 ]

Loop Step i = 0:
   rob  = nums[0] + DP[2] = 1 + 3 = 4
   skip = DP[1]           = 3
   DP[0] = Math.max(4, 3) = 4
DP State Array Final:  [ 4 | 3 | 3 | 1 ]

Result at DP[0] = 4

Java Implementation: House Robber Bottom-Up

public class HouseRobberBottomUp {
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int[] dp = new int[n];

        // Step 1: Base Case Initialization
        dp[n - 1] = nums[n - 1];
        dp[n - 2] = Math.max(nums[n - 1], nums[n - 2]);

        // Step 2: Build table in reverse order
        for (int i = n - 3; i >= 0; i--) {
            int rob = nums[i] + dp[i + 2];
            int skip = dp[i + 1];
            dp[i] = Math.max(rob, skip);
        }

        // Step 3: Global optimal solution is stored at index 0
        return dp[0];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max Loot: " + rob(nums)); // Output: 4
    }
}

9. House Robber — Paradigm #3: Space Optimization

Analyzing the tabulation expression $DP[i] = \max(\text{nums}[i] + DP[i+2], DP[i+1])$, index $i$ only requires $DP[i+1]$ (let's call it next1) and $DP[i+2]$ (let's call it next2). We can eliminate the entire DP array in favor of two state pointers.

Pointer Shifting Walkthrough

Initial Pointers (End of Array):
[ 1  ,  2  ,  3  ,  1 ]
              ^     ^
            next1  next2
          (val=3) (val=1)

Iteration i = 1 (House value 2):
   curr = Math.max(nums[1] + next2, next1)
        = Math.max(2 + 1, 3) = 3
   
   Shift Pointers:
   next2 = next1  =>  3
   next1 = curr   =>  3

Iteration i = 0 (House value 1):
   curr = Math.max(nums[0] + next2, next1)
        = Math.max(1 + 3, 3) = 4
   
   Shift Pointers:
   next2 = next1  =>  3
   next1 = curr   =>  4

Final Result: next1 = 4

Java Implementation: House Robber Space Optimized

public class HouseRobberSpaceOptimized {
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        // Base states representing DP[n-1] and DP[n-2]
        int next2 = nums[n - 1];
        int next1 = Math.max(nums[n - 1], nums[n - 2]);

        for (int i = n - 3; i >= 0; i--) {
            int curr = Math.max(nums[i] + next2, next1);
            next2 = next1;
            next1 = curr;
        }

        return next1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max Loot: " + rob(nums)); // Output: 4
    }
}

10. Architectural Blueprint & Technical Decision Matrix

Solution Architecture Comparison: House Robber Problem

Real-World Engineering Rule of Thumb

Interview System Protocol:

1. Phase 1: Start by articulating the top-down recursive decision tree to demonstrate understanding of overlapping subproblems and optimal substructure.
2. Phase 2: Add a lookup array to formalize Top-Down Memoization ($O(N)$ Time, $O(N)$ Space).
3. Phase 3: Convert the dynamic recurrence logic into an iterative Bottom-Up Tabulation table ($O(N)$ Time, $O(N)$ Space) to eliminate recursive stack overhead.
4. Phase 4: Identify localized state dependency windows (e.g., $i+1$ and $i+2$) to compress space complexity down to constant memory ($O(N)$ Time, $O(1)$ Space).

11. Summary and Key Takeaways

• Dynamic Programming Objective: Eliminates repeated computation by solving every unique subproblem only once and storing its result in memory.
• Prerequisite Properties: Dynamic Programming is strictly applicable to problems exhibiting Overlapping Subproblems and Optimal Substructure.
• Top-Down (Memoization): Combines standard recursive call trees with a dynamic memo structure (cache). It starts from the target problem and moves down toward base cases.
• Bottom-Up (Tabulation): An iterative, non-recursive technique that initializes base cases in a DP table and fills it sequentially toward the final solution.
• Recursion Stack Mitigation: Tabulation avoids deep recursive call stacks, preventing potential runtime StackOverflowError exceptions in systems with large inputs.
• Space Optimization: When state transitions depend on a fixed window of previous entries (such as $i-1, i-2$ or $i+1, i+2$), full $1\text{D}$ or $2\text{D}$ tables can be compressed into constant $O(1)$ scalar state variables.
• The House Robber Decision Pattern: Illustrates the standard choice model: rob = nums[i] + solve(i + 2) vs. skip = solve(i + 1). The optimal state is computed via Math.max(rob, skip).