Dynamic Programming

DP Introduction

Optimization technique for problems with overlapping subproblems and optimal substructure. Store solutions to subproblems to avoid recomputation.

Approach	Direction	Storage	When to Use
Memoization (Top-Down)	Recursion with caching	HashMap or Array	Easier to implement, not all subproblems needed
Tabulation (Bottom-Up)	Iterative, build from base	DP Table (Array)	Better for all subproblems, can optimize space

// DP Problem Recognition
// 1. Can we break into smaller subproblems? (Optimal Substructure)
// 2. Do subproblems repeat? (Overlapping Subproblems)
// 3. What are the states? (What changes between subproblems)
// 4. What is the recurrence relation?
// 5. What are base cases?

// Example: Fibonacci
// Subproblems: fib(n) depends on fib(n-1), fib(n-2)
// Overlapping: fib(5) calls fib(3) twice
// States: Current index n
// Recurrence: fib(n) = fib(n-1) + fib(n-2)
// Base: fib(0) = 0, fib(1) = 1

Understanding the 5-Step DP Framework:

Subproblems: Break the big problem into smaller, similar problems
Overlapping: Check if same subproblems are solved multiple times
States: Identify what variables define each unique subproblem
Recurrence: Write the formula that relates subproblems
Base cases: Define the simplest cases that don't need recursion

Top-Down vs Bottom-Up Comparison

┌─────────────────────────────────────────────────────────────────────────────┐
│                    TOP-DOWN (Memoization)                                   │
│  ┌─────────────────────────────────────────────────────────────────────┐   │
│  │  fib(5) ──────────────────────────────────────────────────────────▶ │   │
│  │    │                                                                │   │
│  │    ├── fib(4) ──────────────────────────────────────────────▶      │   │
│  │    │     ├── fib(3) ───────────────────────────────▶ CACHE!        │   │
│  │    │     │     ├── fib(2) ───────────────▶ CACHE!                  │   │
│  │    │     │     │     ├── fib(1) = 1                                 │   │
│  │    │     │     │     └── fib(0) = 0                                 │   │
│  │    │     │     └── fib(1) = 1                                       │   │
│  │    │     └── fib(2) ───────────────▶ RETURN FROM CACHE ✓           │   │
│  │    └── fib(3) ───────────────────────────────▶ RETURN FROM CACHE ✓ │   │
│  │                                                                     │   │
│  │  Direction: Start from n, recurse down to base cases                │   │
│  │  Storage: Cache results as we return from recursion                 │   │
│  └─────────────────────────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────────┐
│                    BOTTOM-UP (Tabulation)                                   │
│  ┌─────────────────────────────────────────────────────────────────────┐   │
│  │  Index:  │  0  │  1  │  2  │  3  │  4  │  5  │                      │   │
│  │  ────────┼─────┼─────┼─────┼─────┼─────┼─────┤                      │   │
│  │  dp[i]:  │  0  │  1  │  1  │  2  │  3  │  5  │  ◀── Answer!        │   │
│  │          │     │     │     │     │     │     │                      │   │
│  │          │ ──▶ │ ──▶ │ ──▶ │ ──▶ │ ──▶ │     │                      │   │
│  │         base  base  dp[0] dp[1] dp[2] dp[3]                         │   │
│  │         case  case   +     +     +     +                            │   │
│  │                     dp[1] dp[2] dp[3] dp[4]                         │   │
│  │                                                                     │   │
│  │  Direction: Start from base cases, build up to n                    │   │
│  │  Storage: Fill table iteratively from left to right                 │   │
│  └─────────────────────────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────────────────────────┘

Fibonacci Patterns

// 1. Naive Recursion - O(2^n) TIME, O(n) SPACE
int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// 2. Memoization (Top-Down) - O(n) TIME, O(n) SPACE
int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// 3. Tabulation (Bottom-Up) - O(n) TIME, O(n) SPACE
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];
    }
    
    return dp[n];
}

// 4. Space Optimized - O(n) TIME, O(1) SPACE
int fibOptimal(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;
}

// Climbing Stairs - Same pattern!
// Ways to reach step n = ways to reach (n-1) + (n-2)
int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// House Robber - Can't rob adjacent houses
int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    
    int prev2 = 0, prev1 = 0;
    
    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

Step-by-Step Breakdown:

Naive Recursion: Exponential O(2ⁿ) - recalculates same values repeatedly
Memoization: Add a cache array, check before computing - reduces to O(n)
Tabulation: Build solution iteratively from base cases - same O(n) but no recursion overhead
Space Optimized: Since we only need last 2 values, use 2 variables instead of array - O(1) space!

Pro Tip: Climbing Stairs and House Robber follow the same pattern! Always look for the recurrence relation: current = f(previous states)

Knapsack Problems

0/1 Knapsack: Given items with weights and values, maximize value within weight capacity. Each item can be taken at most once.

// 0/1 Knapsack - O(n*W) TIME, O(n*W) SPACE
int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            // Don't take item i
            dp[i][w] = dp[i - 1][w];
            
            // Take item i (if possible)
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            }
        }
    }
    
    return dp[n][W];
}

// Space Optimized - O(W) SPACE
int knapsackOptimized(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < weights.length; i++) {
        // Traverse right to left to avoid using updated values
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    
    return dp[W];
}

// Coin Change - Minimum coins (Unbounded Knapsack)
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

// Coin Change 2 - Number of ways
int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    // Iterate coins first to avoid counting permutations
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}

// Subset Sum - Can we form target sum?
boolean canPartition(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

Knapsack Family Explained:

Problem	Key Insight	Loop Direction
0/1 Knapsack	Take or skip each item (once)	Right → Left (prevent reuse)
Unbounded Knapsack	Unlimited items allowed	Left → Right (allow reuse)
Coin Change (min)	Minimum coins needed	Left → Right, use min()
Coin Change (ways)	Count combinations	Coins outer, amount inner
Subset Sum	Boolean: can we make sum?	Right → Left, use OR

Critical: In 0/1 Knapsack, traverse right-to-left to ensure each item is used at most once. Left-to-right would allow using the same item multiple times!

Memoization Table Visualization (Knapsack)

Example: weights = [1, 2, 3], values = [6, 10, 12], capacity = 5

       Capacity →
         0    1    2    3    4    5
      ┌────┬────┬────┬────┬────┬────┐
Item 0│  0 │  0 │  0 │  0 │  0 │  0 │  (no items)
  ↓   ├────┼────┼────┼────┼────┼────┤
Item 1│  0 │  6 │  6 │  6 │  6 │  6 │  (item: w=1, v=6)
      ├────┼────┼────┼────┼────┼────┤
Item 2│  0 │  6 │ 10 │ 16 │ 16 │ 16 │  (item: w=2, v=10)
      ├────┼────┼────┼────┼────┼────┤
Item 3│  0 │  6 │ 10 │ 16 │ 18 │ 22 │  (item: w=3, v=12)
      └────┴────┴────┴────┴────┴────┘
                                  ↑
                           Answer: 22

Recurrence: dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
                           skip item      take item (if weight fits)

LCS & LIS

Longest Common Subsequence

// LCS - O(m*n) TIME, O(m*n) SPACE
int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

// LCS with reconstruction
String getLCS(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // Build DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // Backtrack to find LCS
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            sb.append(text1.charAt(i - 1));
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return sb.reverse().toString();
}

Longest Increasing Subsequence

// LIS - O(n²) DP
int lengthOfLIS_DP(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// LIS - O(n log n) Binary Search
int lengthOfLIS(int[] nums) {
    List sub = new ArrayList<>();
    
    for (int num : nums) {
        int pos = binarySearch(sub, num);
        
        if (pos == sub.size()) {
            sub.add(num);
        } else {
            sub.set(pos, num);
        }
    }
    
    return sub.size();
}

// Find first position >= target
int binarySearch(List sub, int target) {
    int left = 0, right = sub.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (sub.get(mid) < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// Edit Distance - Levenshtein Distance
int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],  // Replace
                               Math.min(dp[i - 1][j],      // Delete
                                        dp[i][j - 1]));    // Insert
            }
        }
    }
    
    return dp[m][n];
}

Subsequence Problems Decoded:

LCS (Two Strings)

Compare chars at each position
If match: dp[i][j] = dp[i-1][j-1] + 1
If no match: max(dp[i-1][j], dp[i][j-1])
Backtrack from dp[m][n] to reconstruct

LIS (Single Array)

O(n²): For each i, check all j < i
O(n log n): Binary search on "tails" array
Key insight: Maintain smallest endings
Similar: Longest Bitonic, Russian Dolls

Grid DP

// Unique Paths - Count ways to reach bottom-right
int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    // First row and column have only 1 way
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
}

// Minimum Path Sum
int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    
    dp[0][0] = grid[0][0];
    
    // First row
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    // First column
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    // Fill rest
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    return dp[m - 1][n - 1];
}

// Maximal Square - Largest square of 1s
int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int maxSide = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(dp[i - 1][j - 1],
                           Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    
    return maxSide * maxSide;
}

// Maximum Subarray - Kadane's Algorithm
int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

Grid DP Patterns:

Problem	What to Track	Recurrence
Unique Paths	Count of ways	`dp[i][j] = dp[i-1][j] + dp[i][j-1]`
Min Path Sum	Minimum cost	`dp[i][j] = min(top, left) + grid[i][j]`
Maximal Square	Side length of largest square	`dp[i][j] = min(top,left,diag) + 1`
Kadane's	Current/Max sum	`curr = max(nums[i], curr + nums[i])`

Space Trick: Most 2D grid DP can be reduced to 1D by only keeping the previous row. For Kadane's, we just need 2 variables!

Practice Problems

Master DP by solving these classic problems! They're ordered by difficulty and cover all major patterns.

Easy Fibonacci Pattern

Climbing Stairs

Count ways to reach the top with 1 or 2 steps at a time.

dp[i] = dp[i-1] + dp[i-2]

LeetCode #70

Medium Fibonacci Pattern

House Robber

Max money without robbing adjacent houses.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

LeetCode #198

Medium Unbounded Knapsack

Coin Change

Fewest coins to make the target amount.

dp[i] = min(dp[i], dp[i-coin] + 1)

LeetCode #322

Medium Two Strings

Longest Common Subsequence

Find the longest subsequence common to both strings.

Match? dp[i-1][j-1]+1 : max(left, up)

LeetCode #1143

Hard 0/1 Knapsack

0/1 Knapsack

Maximize value within weight limit. Each item once.

dp[w] = max(dp[w], val[i] + dp[w-wt[i]])

GeeksforGeeks

Hard Grid DP

Edit Distance

Min operations to convert word1 to word2.

dp[i][j] = min(replace, insert, delete)

LeetCode #72

Interview Tip: Most DP interview questions are variations of these 5 patterns: Fibonacci, Knapsack, LCS/LIS, Grid DP, and Interval DP. Master these and you'll recognize 90% of DP problems!

Key Takeaways

Identify DP Problems

Look for overlapping subproblems and optimal substructure.

Top-Down = Memoization

Recursive with caching. Easier to implement.

Bottom-Up = Tabulation

Iterative, build from base cases. Can optimize space.

Space Optimization

Often can reduce O(n²) space to O(n) or O(1).

Dynamic Programming

What You'll Learn

Contents

DP Introduction