Dynamic Programming

advanced5 problems· Prerequisites: Big O & Complexity, Arrays & Strings, Recursion & Backtracking

What is Dynamic Programming?

Dynamic Programming = recursion + memoization.

Solve problems by breaking them into overlapping subproblems and caching results.

Two approaches:

Top-down (memoization) - recursive with cache
Bottom-up (tabulation) - iterative, filling a table

When to use DP:

Problem asks for count, max/min, or true/false (is it possible?)
Problem can be broken into smaller subproblems
Subproblems overlap (not just divide & conquer)

DP is NOT needed when: Subproblems don't overlap (use divide & conquer) or greedy works.

Problem

Climbing Stairs: how many distinct ways can you reach step n if you can climb 1 or 2 steps at a time?

Climbing Stairs: Bottom-Up DPStep 1 / 9

Step 0

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

We will compute how many ways there are to reach each step, from bottom up.

Speed:

Base case Referenced Computing Done

Top-down vs bottom-up (Fibonacci)C#

// Top-down (memoization) - O(n) time, O(n) space
int FibMemo(int n, Dictionary<int, int> memo = null) {
    memo ??= new Dictionary<int, int>();
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}

// Bottom-up (tabulation) - O(n) time, O(1) space
int FibTab(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

// Bottom-up (full table) - O(n) time, O(n) space
int FibTable(int n) {
    if (n <= 1) return n;
    var 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];
}

1D DP Patterns

Pattern 1: Climbing stairs / Fibonacci-like dp[i] = dp[i-1] + dp[i-2]

Pattern 2: House robber (adjacent skip) dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Pattern 3: Longest Increasing Subsequence (LIS) dp[i] = 1 + max(dp[j]) for j < i and nums[j] < nums[i]

Pattern 4: Partition (subset sum / coin change) dp[i] = dp[i] OR dp[i - coin] (for boolean) dp[i] = min(dp[i], dp[i - coin] + 1) (for minimum coins)

Classic 1D DP problemsC#

// House Robber - O(n), O(1) space
int Rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    foreach (var n in nums) {
        int curr = Math.Max(prev1, prev2 + n);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// Climbing Stairs - O(n), O(1) space
int ClimbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

// Coin Change (minimum coins) - O(amount * coins), O(amount) space
int CoinChange(int[] coins, int amount) {
    var dp = new int[amount + 1];
    Array.Fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        foreach (var coin in coins) {
            if (coin <= i)
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

2D DP Patterns

Pattern 1: Grid paths (Unique Paths) dp[i][j] = dp[i-1][j] + dp[i][j-1]

Pattern 2: Longest Common Subsequence (LCS) dp[i][j] = dp[i-1][j-1] + 1 if match, else max(dp[i-1][j], dp[i][j-1])

Pattern 3: Edit Distance dp[i][j] = min(insert, delete, replace)

Pattern 4: 0/1 Knapsack dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)

2D DP templatesC#

// Longest Common Subsequence - O(m*n)
int LCS(string text1, string text2) {
    int m = text1.Length, n = text2.Length;
    var dp = new int[m + 1, n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[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];
}

// 0/1 Knapsack - O(n * capacity)
int Knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.Length;
    var dp = new int[n + 1, capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w)
                dp[i, w] = Math.Max(
                    dp[i - 1, w],
                    dp[i - 1, w - weights[i - 1]] + values[i - 1]
                );
            else
                dp[i, w] = dp[i - 1, w];
        }
    }
    return dp[n, capacity];
}

When to Use Dynamic Programming

DP is powerful but often overused. Here's a decision framework:

Signal	Use DP	Don't Use DP
Problem asks for count of ways	Strong DP signal	If greedy always works
Problem asks for max/min under constraints	Likely DP	If greedy choice property holds
Problem asks "is it possible?"	DP or BFS	If simple rule works
Subproblems overlap	DP needed	Divide & conquer suffices
Can make local optimal choice	Greedy probably works	Use greedy instead
Subproblems don't overlap	DP won't help	Use divide & conquer

Rule of thumb: If you can state "the answer for input X depends on the answer for smaller inputs X₁, X₂, ..." and those smaller inputs are reused, it's DP.

When NOT to use DP:

Greedy works (activity selection, Dijkstra's)
Simple formula exists (sum 1..n = n(n+1)/2)
Input is tiny (brute force is simpler)
Subproblems don't overlap (pure divide & conquer)

Interview red flag: If you start memoizing every recursive function "just in case", you're probably over-engineering. Ask: "Do subproblems actually repeat?"

Common Mistakes / Gotchas

Wrong base case A single off-by-one in the base case propagates to every computed value. Always test small inputs (n=0, n=1, n=2) before scaling up.

Wrong iteration order in bottom-up DP If dp[i] depends on dp[i-1], you iterate forward. If it depends on dp[i+1], you iterate backward. Getting this wrong uses stale or uninitialized values.

Forgetting to pass the memo dictionary In top-down DP, if you create a new memo on each recursive call, nothing is cached and you're back to exponential time. Pass the memo by reference.

"I can use DP for everything" DP is only for problems with overlapping subproblems. If subproblems don't overlap (divide and conquer), DP adds unnecessary complexity. If greedy works, DP is overkill.

Confusing 0/1 knapsack with unbounded knapsack In 0/1 knapsack, each item can be used at most once (iterate items outer loop, capacity inner loop). In unbounded knapsack, items can be reused (iterate capacity outer loop, coins inner loop). Swapping the loops gives wrong answers.

DP array size off-by-one dp[n] for an n-element problem often needs size n+1 (dp[0] for empty/base case). Forgetting the extra slot causes index out of bounds.

Common Interview Patterns

Fibonacci-style - climbing stairs, house robber, decode ways
Grid DP - unique paths, min path sum, maximal square
Two sequences - LCS, edit distance, wildcard matching
Knapsack / subset sum - partition equal subset sum, coin change
DP on intervals - burst balloons, matrix chain multiplication
DP on trees - tree diameter, max path sum (post-order traversal)

Quick checklist to find the DP recurrence:

Define the state (what does dp[i] represent?)
Find the recurrence (how does dp[i] relate to previous states?)
Set base cases
Determine iteration order

Wrong base case A single off-by-one in the base case propagates to every computed value. Always test small inputs (n=0, n=1, n=2) before scaling up.

Forgetting to pass the memo dictionary In top-down DP, if you create a new memo on each recursive call, nothing is cached and you're back to exponential time. Pass the memo by reference.

DP array size off-by-one dp[n] for an n-element problem often needs size n+1 (dp[0] for empty/base case). Forgetting the extra slot causes index out of bounds.