Dynamic Programming

advanced5 problems

Prerequisites:Big O & ComplexityArrays & StringsRecursion & Backtracking

The Problem with "Try Everything"

Dynamic Programming is the most feared topic in DSA interviews - but also the most rewarding once it clicks.

In the Recursion module, you learned backtracking - try every possibility, undo, try the next. That works for small problems, but some problems have overlapping subproblems: the same subproblem gets solved thousands of times.

Remember naive Fibonacci? fib(5) calls fib(3) twice and fib(2) three times. As n grows, the redundant work explodes exponentially.

Dynamic Programming = recursion + caching. You solve each subproblem once, store the result, and reuse it whenever the same subproblem appears again.

The name is confusing - it's not "dynamic" and it's not "programming" in the coding sense. It's really just smart brute force: avoid repeating work you've already done.

What is Dynamic Programming?

Dynamic Programming = smart recursion - you solve each subproblem once and cache the result.

Two approaches:

Top-down (memoization) - recursive with a cache (dictionary/array). Same structure as the naive solution, but with a "check cache before computing" step.
Bottom-up (tabulation) - iterative, filling a table from smallest to largest. Often more efficient and avoids recursion depth limits.

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 Not yet computed

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

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.

Key Patterns to Remember

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

You've Reached the End

Congratulations - you've made it through all 11 modules of Zero To DSA!

You started with Big O, learning to talk about algorithm speed. You built up through arrays, hash maps, linked lists, stacks, and queues. You tackled recursion, sorting, trees, and graphs. And you finished with the two advanced strategies: dynamic programming and greedy algorithms.

You now have a mental toolbox of data structures and algorithms. When you encounter a new problem, you can ask:

What's the input size? (Big O)
Does order matter? (Array vs HashSet vs Tree)
Is it hierarchical? (Tree) or connected? (Graph)
Should I explore all possibilities? (Recursion/Backtracking)
Should I cache results? (DP)
Or is the greedy choice always optimal? (Greedy)

The rest is practice. Each problem you solve will strengthen these mental muscles. Good luck!

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.