Week 13: Dynamic Programming I: Foundations

1. Memoization vs. Tabulation

Dynamic programming applies when a problem has overlapping subproblems (the same smaller question gets asked repeatedly) and optimal substructure (an optimal answer can be built from optimal answers to subproblems). Fibonacci is the smallest example: the naive recursion recomputes fib(3) many times while computing fib(6).

fibonacci.cpp

#include <vector>
using namespace std;

// Naive recursion -- O(2^n), massive redundant recomputation
int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// Top-down MEMOIZATION -- O(n) time, O(n) space (cache + call stack)
int fibMemo(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) 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 prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Memoization keeps the original recursive structure and adds a cache — it's usually the fastest way to turn a working brute-force recursion into a DP solution. Tabulation rebuilds the same answer bottom-up in a loop, avoiding recursion overhead and often letting you shrink the cache down to O(1) space once you notice a state only depends on the last one or two rows.

Write the brute-force recursion first, always

Trying to write a tabulated DP solution directly is where most learners get stuck. Write the naive recursive solution, identify what changes between calls (the "state"), add a cache keyed by that state, and only convert to tabulation once the memoized version is correct.

2. 1D DP: Climbing Stairs & House Robber

1D DP problems define dp[i] as the answer considering only the first i elements or the first i steps, then express dp[i] in terms of a small number of earlier states.

one_d_dp.cpp

#include <vector>
#include <algorithm>
using namespace std;

// Climbing Stairs: ways to reach step n, taking 1 or 2 steps at a time
// dp[i] = dp[i-1] + dp[i-2] -- O(n) time, O(1) space
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: max sum of non-adjacent elements
// dp[i] = max(dp[i-1], dp[i-2] + nums[i]) -- O(n) time, O(1) space
int rob(const vector<int>& nums) {
    int prevNoTake = 0, prevTake = 0;
    for (int x : nums) {
        int curr = max(prevTake, prevNoTake + x);
        prevNoTake = prevTake;
        prevTake = curr;
    }
    return prevTake;
}

State your recurrence in words first

Before writing a single line of code, say the recurrence out loud: "dp[i] equals the best answer using only the first i houses, which is either skip house i and keep dp[i-1], or take house i's value plus dp[i-2]." That habit scales to every DP problem you'll meet this week and next.

3. Longest Increasing Subsequence

LIS asks for the length of the longest subsequence (not necessarily contiguous) where each element is strictly greater than the last. The straightforward DP defines dp[i] as the LIS length ending exactly at index i:

lis.cpp

#include <vector>
#include <algorithm>
using namespace std;

// O(n^2): dp[i] = length of the LIS ending exactly at index i
int lengthOfLIS_On2(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    return best;
}

// O(n log n): maintain the smallest possible tail for each subsequence length
int lengthOfLIS_NLogN(const vector<int>& nums) {
    vector<int> tails;   // tails[k] = smallest tail of an increasing subsequence of length k+1
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

The tails array isn't a real subsequence

It's tempting to assume tails holds an actual increasing subsequence from the input — it doesn't, since earlier entries can get overwritten by smaller values found later. What's guaranteed is only its LENGTH: reconstructing the actual subsequence needs extra bookkeeping (a parent-index array) alongside this trick.

4. 2D DP: 0/1 Knapsack

0/1 knapsack maximizes total value within a weight capacity, where each item can be used at most once. dp[i][w] is the best value achievable using the first i items with capacity w — for each item you either skip it or take it, never both:

knapsack.cpp

#include <vector>
#include <algorithm>
using namespace std;

// O(n * W) time and space
int knapsack(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w];   // skip item i-1
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

// Space-optimized: only the previous row is ever needed -- O(W) space
int knapsackOptimized(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {   // iterate DOWN to avoid reusing item i
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Why the space-optimized loop goes backward

Iterating w downward guarantees dp[w - weights[i]] still holds last iteration's (item i-1's) value when you read it — iterating upward would read a value already updated for item i, silently allowing the same item to be counted twice. This "why backward" question is a favorite interview follow-up.

5. Edit Distance

Edit distance finds the minimum number of insertions, deletions, and substitutions needed to turn one string into another. dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2:

edit_distance.cpp

#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// O(m * n) time and space
int editDistance(const string& word1, const string& word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = i;   // delete all of word1
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // insert all of word2

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];   // characters match -- no edit needed
            } else {
                dp[i][j] = 1 + min({ dp[i - 1][j],       // delete from word1
                                      dp[i][j - 1],       // insert into word1
                                      dp[i - 1][j - 1] }); // replace
            }
        }
    }
    return dp[m][n];
}

Get the base row and column right first

dp[i][0] = i ("delete everything") and dp[0][j] = j ("insert everything") anchor every other cell in the table — a mistake there silently corrupts the entire grid, since every interior cell's value ultimately traces back to these base cases.

6. Hands-on Exercise

Hands-on

Build a Dynamic Programming Toolkit

Implement this week's five DP patterns and confirm each one against a brute-force or alternate version.

Requirements:

Implement fibMemo and fibTab, confirm identical results for n up to 40, and time fibNaive vs. fibMemo at n = 35 to see the real cost of unmemoized overlapping subproblems.
Implement rob (House Robber), then extend it to robCircular(nums) for houses arranged in a circle by running the linear version twice on two overlapping sub-ranges that each exclude one end.
Implement lengthOfLIS_NLogN and verify it matches lengthOfLIS_On2 on at least five test vectors, including one with duplicate values.
Implement both knapsack and knapsackOptimized and confirm they return identical results on the same inputs.
Implement editDistance and check it against a known case ("horse" to "ros" should return 3).

Hint

For the circular robber, the answer is max(rob(nums[0..n-2]), rob(nums[1..n-1])) — excluding one end each time handles the wrap-around adjacency between the first and last house without any new DP logic.

7. Knowledge Check

Four quick questions. Expand each to check your answer.

What are the two properties a problem must have for dynamic programming to apply, and how do you spot them in a new problem?

A problem needs overlapping subproblems (the same smaller question gets asked more than once by different branches of the recursion) and optimal substructure (an optimal overall answer can be assembled from optimal answers to those subproblems). You spot the first by drawing the recursion tree for a brute-force solution and looking for repeated calls with identical arguments, and the second by checking whether a greedy or divide-and-conquer choice at each step still leads to a correct global answer.

In the 0/1 knapsack space-optimized solution, why must the inner loop over capacity `w` iterate downward instead of upward?

The 1D array reuses the same memory for both "row i-1" and "row i," so when computing dp[w] for the current item, dp[w - weights[i]] needs to still hold last item's value. Iterating downward guarantees that cell hasn't been overwritten yet for the current item; iterating upward would read an already-updated value, effectively allowing the same item to be included more than once.

Why does the O(n log n) LIS algorithm's `tails` array give the correct LENGTH of the LIS even though it isn't necessarily a real subsequence from the input?

tails[k] always holds the smallest possible tail value among all increasing subsequences of length k+1 seen so far, and keeping that tail as small as possible only ever helps extend to a longer subsequence later — it never hurts. Because every valid increasing subsequence length that could exist is represented by some prefix of tails, the array's final size exactly equals the true LIS length, even though the specific values stored may never have appeared together in the original input.

In the edit distance recurrence, why does a mismatched character cost `1 + min(delete, insert, replace)` rather than always using one fixed operation?

At each mismatched pair of characters, any of the three operations could turn out to be part of the optimal overall edit sequence depending on what the rest of the two strings look like, so the recurrence has to consider all three and pick whichever leaves the smallest remaining subproblem. Hardcoding one operation would give the wrong answer on strings where, say, an insertion happens to be cheaper than a substitution at that position.