Dynamic Programming | Phase 3

5-Step DP Framework

Identify

Overlapping subproblems? Optimal substructure?

Define State

What does dp[i] or dp[i][j] represent?

Recurrence

How does dp[i] relate to smaller states?

Base Cases

What are the smallest valid states?

Optimize

Top-down memo or bottom-up table?

Top-Down vs Bottom-Up

C++
// Problem: Fibonacci number
// TOP-DOWN (memoization) — natural, recursive, lazy evaluation
vector<int> memo(n+1, -1);
int fib(int n) {
    if (n<=1) return n;
    if (memo[n]!=-1) return memo[n];   // already computed
    return memo[n] = fib(n-1) + fib(n-2);
}

// BOTTOM-UP (tabulation) — iterative, fills table from base cases up
int fib(int n) {
    if (n<=1) return n;
    vector<int> dp(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];
}

// SPACE OPTIMIZED — only keep last 2 values
int fib(int n) {
    if(n<=1) return n;
    int a=0, b=1;
    for(int i=2; i<=n; i++) { int c=a+b; a=b; b=c; }
    return b;
}  // Space: O(1) !
    

Interactive: Coin Change DP Table

Bottom-up fill of dp[0..5] for coins=[1,2,5], amount=5. Each cell shows the minimum coins needed for that amount — built from base case dp[0]=0 upward.

DP Problem Categories

1D DP (Linear)

Climbing Stairs
House Robber
Coin Change
Longest Increasing Subsequence

2D DP (Grid/Matrix)

Unique Paths
Edit Distance
Longest Common Subsequence
0/1 Knapsack

Interval DP

Burst Balloons
Matrix Chain Multiplication
Palindrome Partitioning

State Machine DP

Stock Buy/Sell with cooldown
Best Time to Buy Stock IV
Paint Fence

Practice Problems

#70Climbing StairsEasy

You can climb 1 or 2 steps at a time. How many ways to reach step n?

State: dp[i] = ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Base: dp[1]=1, dp[2]=2.

C++
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;
}
// Time: O(n)  Space: O(1)

#198House RobberMedium

Rob maximum money without robbing two adjacent houses.

State: dp[i] = max money from first i houses. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

C++
int rob(vector<int>& nums) {
    int n=nums.size();
    if(n==1) return nums[0];
    int prev2=nums[0], prev1=max(nums[0],nums[1]);
    for(int i=2;i<n;i++) {
        int cur=max(prev1, prev2+nums[i]);
        prev2=prev1; prev1=cur;
    }
    return prev1;
}
// Time: O(n)  Space: O(1)

#322Coin ChangeMedium

Given coin denominations and target amount, find minimum number of coins to make the amount. Return -1 if impossible.

State: dp[i] = min coins to make amount i. Recurrence: dp[i] = 1 + min(dp[i - coin]) for all coins ≤ i.

C++
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);  // init to impossible value
    dp[0] = 0;
    for(int i=1;i<=amount;i++)
        for(int c:coins)
            if(c<=i) dp[i]=min(dp[i], dp[i-c]+1);
    return dp[amount]>amount ? -1 : dp[amount];
}
// Time: O(amount * coins)  Space: O(amount)

#300Longest Increasing SubsequenceMedium

Find the length of the longest strictly increasing subsequence.

O(n²) DP: dp[i] = LIS ending at i = 1 + max(dp[j]) where j < i and nums[j] < nums[i]. O(n log n): patience sort with binary search.

C++
// O(n log n) — binary search approach
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;  // tails[i] = smallest tail of IS with length i+1
    for(int n : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), n);
        if(it==tails.end()) tails.push_back(n);  // extend LIS
        else *it=n;                               // replace to keep smallest tail
    }
    return tails.size();
}
// Time: O(n log n)  Space: O(n)

#1143Longest Common SubsequenceMedium

Find the length of the longest common subsequence of two strings.

State: dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]. If chars match: dp[i][j] = dp[i-1][j-1]+1. Else: max(dp[i-1][j], dp[i][j-1]).

C++
int longestCommonSubsequence(string t1, string t2) {
    int m=t1.size(), n=t2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1,0));
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) {
        if(t1[i-1]==t2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
        else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
    }
    return dp[m][n];
}
// Time: O(m*n)  Space: O(m*n)

#72Edit DistanceMedium

Minimum operations (insert, delete, replace) to convert word1 to word2.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. If chars match, no cost. Else: 1 + min(insert, delete, replace).

C++
int minDistance(string w1, string w2) {
    int m=w1.size(), n=w2.size();
    vector<vector<int>> dp(m+1, vector<int>(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(w1[i-1]==w2[j-1]) dp[i][j]=dp[i-1][j-1];
        else dp[i][j]=1+min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
    }
    return dp[m][n];
}
// Time: O(m*n)  Space: O(m*n)

#416Partition Equal Subset SumMedium

Determine if array can be partitioned into two subsets with equal sums.

Pattern: 0/1 Knapsack. Check if sum/2 is achievable. dp[j] = can we make sum j using elements so far? Process backwards to avoid reuse.

C++
bool canPartition(vector<int>& nums) {
    int sum=accumulate(nums.begin(),nums.end(),0);
    if(sum%2) return false;
    int target=sum/2;
    vector<bool> dp(target+1,false); dp[0]=true;
    for(int n:nums)
        for(int j=target;j>=n;j--)  // backwards = 0/1 knapsack
            dp[j]=dp[j]||dp[j-n];
    return dp[target];
}
// Time: O(n * sum)  Space: O(sum)

#312Burst BalloonsHard

Burst balloons to maximize coins. Bursting balloon i gives nums[left]*nums[i]*nums[right]. Find max coins.

Key insight: Think of which balloon you burst LAST in a range, not first. dp[i][j] = max coins from bursting all balloons between i and j (exclusive). Try each as last.

C++
int maxCoins(vector<int>& nums) {
    nums.insert(nums.begin(), 1); nums.push_back(1);  // sentinel
    int n=nums.size();
    vector<vector<int>> dp(n, vector<int>(n,0));
    for(int len=2;len<n;len++) {  // length of range
        for(int l=0;l<n-len;l++) {
            int r=l+len;
            for(int k=l+1;k<r;k++)  // k = last balloon burst in (l,r)
                dp[l][r]=max(dp[l][r], dp[l][k]+nums[l]*nums[k]*nums[r]+dp[k][r]);
        }
    }
    return dp[0][n-1];
}
// Time: O(n³)  Space: O(n²)

The DP shortcut: If you can write a correct recursive solution, you already have a DP solution — just add memoization. Then if needed, convert to bottom-up by reversing the recursion order. Never jump to DP before understanding the recursion.

Deeper Understanding

How to Actually Identify and Solve DP Problems

Spotting Overlapping Subproblems

Draw the recursion tree first

For fib(5), the recursion tree computes fib(3) twice, fib(2) three times, fib(1) five times. If any node repeats, memoization will help. If no nodes repeat, DP adds overhead for nothing.

DP requires optimal substructure too

Not all problems with overlapping subproblems are DP. The optimal solution to the whole must be built from optimal solutions to subproblems. Longest path in a DAG is DP; shortest path in a graph with cycles requires Dijkstra/Bellman-Ford.

Signal phrases in the problem

"Minimum number of…", "maximum profit…", "number of ways to…", "can you achieve…" — these are DP signals. Contrast with "find all solutions" which is backtracking.

Top-down vs Bottom-up: When to Use Which

Top-down (memoization) is easier to write

Write the natural recursion, then add a cache. Only computes states that are actually needed — good when many states are unreachable (sparse DP). Risk: stack overflow for large n (Python recursion limit, deep call stacks).

Bottom-up (tabulation) is faster in practice

No function call overhead, no recursion depth risk. Cache access patterns are sequential — CPU-cache friendly. Required when you need to optimize space (rolling array only works bottom-up).

Space optimization: rolling array

For Fibonacci: dp[i] only depends on dp[i-1] and dp[i-2], so keep only two variables. For LCS: each row only needs the previous row — reduce O(mn) to O(min(m,n)).

Common Off-by-One and Direction Errors

0/1 Knapsack: must iterate backwards

In the 1D knapsack optimization, iterate j from target down to coin. Forward iteration allows reusing the same item multiple times (unbounded knapsack). Get the direction wrong and you silently solve the wrong problem.

State definition is everything

Bugs usually stem from a vague state. "dp[i] = answer for first i items" is underspecified — answer with or without item i? When the state is precise, the recurrence writes itself.

Interval DP: loop order matters

For Burst Balloons, iterate by length of interval (outer loop), then by left endpoint (inner loop). This ensures smaller subintervals are solved before larger ones that depend on them.