DP Introduction

Dynamic Programming is an algorithmic technique that solves complex problems by breaking them into overlapping subproblems and storing their solutions.

Two Key Properties

1. Overlapping Subproblems: Same subproblems are solved repeatedly
2. Optimal Substructure: Optimal solution contains optimal solutions to subproblems

Fibonacci Example: The Problem with Naive Recursion

// Naive recursion - O(2^n) time, O(n) space (call stack)
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // Redundant calls!
}

// fib(5) calls fib(4) and fib(3)
// fib(4) calls fib(3) and fib(2)
// fib(3) is computed TWICE → wasteful

Memoization (Top-Down DP)

Store results of subproblems as they're computed. Start from the original problem and work down.

// Memoization - O(n) time, O(n) space
public int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // Return cached result
    
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Usage:
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
int result = fibMemo(n, memo);

Tabulation (Bottom-Up DP)

Solve subproblems starting from the smallest and build up to the original problem.

// Tabulation - O(n) time, O(n) space
public int fibTab(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // State transition
    }
    
    return dp[n];
}

Space-Optimized Tabulation

// O(n) time, O(1) space - only need last two values
public int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

Comparison

Aspect	Memoization	Tabulation
Direction	Top-down	Bottom-up
Subproblems	Lazy (compute when needed)	Eager (compute all)
Recursion	Uses call stack	Uses array/list
Space	O(n) call stack	O(n) array (can be optimized)
Speed	Slightly slower (call overhead)	Slightly faster (no recursion)

When to Use Which?

• Memoization: When not all subproblems need to be solved
• Tabulation: When all subproblems must be solved, or to avoid recursion depth limits
• Space optimization: When recurrence only depends on a few previous values

Recognizing DP Problems

Ask yourself these questions:

1. Does the problem ask for optimal value (min/max/longest/shortest)?
2. Does it involve choices or decisions at each step?
3. Can the problem be broken into overlapping subproblems?

The 5 Steps to Solve Any DP Problem

1. Define state: What does dp[i] or dp[i][j] represent?
2. Base case: What are the trivial cases?
3. State transition: How do you compute dp[i] from smaller subproblems?
4. Order of computation: Which subproblems must be solved first?
5. Extract answer: Which dp value is the final answer?

Climb Stairs Problem

// You can climb 1 or 2 steps. How many distinct ways to reach step n?
public int climbStairs(int n) {
    if (n <= 2) return n;
    
    int[] dp = new int[n + 1];
    dp[1] = 1;  // Base case: 1 way to reach step 1
    dp[2] = 2;  // Base case: 2 ways to reach step 2
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // From step i-1 (1 step) or i-2 (2 steps)
    }
    
    return dp[n];
}

State: dp[i] = number of distinct ways to reach step i
Base: dp[1] = 1, dp[2] = 2
Transition: dp[i] = dp[i-1] + dp[i-2]

Common DP Patterns

Pattern	Example Problems
Linear DP	Climbing stairs, House robber, Maximum subarray
Grid DP	Unique paths, Minimum path sum, Dungeon game
Knapsack	0/1 Knapsack, Subset sum, Partition equal
String DP	Edit distance, Longest common subsequence
Interval DP	Matrix chain multiplication, Burst balloons

Debugging DP Solutions

// Print the DP table to verify
for (int i = 0; i <= n; i++) {
    System.out.println("dp[" + i + "] = " + dp[i]);
}

// Or trace through small input manually
// Verify base cases and transitions are correct

Amazon Interview Tips

• Start with brute force recursive solution
• Identify overlapping subproblems
• Add memoization first (easier to get right)
• Optimize space if time allows
• Always discuss time/space complexity
• Handle edge cases: n=0, n=1, negative values