Dynamic Programming — 42 Problems, Table by Table

Given n items each with a weight and a value, and a knapsack of capacity W, pick a subset of items with total weight ≤ W that maximises total value. Each item may be taken at most once (that is the “0/1” part — no fractions, no repeats).

dp[0][c] = 0,  dp[i][0] = 0
dp[i][c] = dp[i-1][c]                                if w[i] > c
dp[i][c] = max( dp[i-1][c],  v[i] + dp[i-1][c-w[i]] )  otherwise

Gold = final answer. Blue = cells on the traceback path (the chosen items).

int knapsack(const vector<int>& w, const vector<int>& v, int W) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int c = 0; c <= W; ++c) {
            dp[i][c] = dp[i-1][c];                    // skip item i
            if (w[i-1] <= c)                          // or take it
                dp[i][c] = max(dp[i][c], v[i-1] + dp[i-1][c - w[i-1]]);
        }
    return dp[n][W];
}

Given two strings, find the length of the longest sequence of characters that appears in both, in the same relative order. The characters need not be contiguous.

dp[0][j] = dp[i][0] = 0
dp[i][j] = dp[i-1][j-1] + 1              if a[i] == b[j]
dp[i][j] = max( dp[i-1][j], dp[i][j-1] )  otherwise

Gold = answer. Blue = matched characters found by walking back from the corner.

int lcs(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
                                          : max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

Find the minimum number of single-character insertions, deletions or substitutions needed to turn one string into another (Levenshtein distance).

dp[i][0] = i   (delete everything),   dp[0][j] = j   (insert everything)
dp[i][j] = dp[i-1][j-1]                                     if a[i] == b[j]
dp[i][j] = 1 + min( dp[i-1][j-1],  dp[i-1][j],  dp[i][j-1] ) otherwise
            substitute    delete      insert

Gold = answer. Blue = one optimal edit path back to the origin.

int editDistance(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            if (i == 0)                 dp[i][j] = j;
            else if (j == 0)            dp[i][j] = i;
            else if (a[i-1] == b[j-1])  dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + min({dp[i-1][j-1],    // substitute
                                     dp[i-1][j],      // delete
                                     dp[i][j-1]});    // insert
        }
    return dp[n][m];
}

Given a set of positive integers and a target T, decide whether some subset adds up to exactly T. Same shape as knapsack, but the table holds booleans.

dp[i][0] = true   (the empty subset),   dp[0][t>0] = false
dp[i][t] = dp[i-1][t]                          if s[i] > t
dp[i][t] = dp[i-1][t]  OR  dp[i-1][t-s[i]]      otherwise

Green = reachable, grey = not. Gold = target. Blue = the numbers picked on the traceback.

bool subsetSum(const vector<int>& s, int T) {
    int n = s.size();
    vector<vector<char>> dp(n + 1, vector<char>(T + 1, false));
    for (int i = 0; i <= n; ++i)
        dp[i][0] = true;                          // empty subset hits 0
    for (int i = 1; i <= n; ++i)
        for (int t = 1; t <= T; ++t) {
            dp[i][t] = dp[i-1][t];
            if (s[i-1] <= t && dp[i-1][t - s[i-1]])
                dp[i][t] = true;
        }
    return dp[n][T];
}

Given coin denominations of unlimited supply, make an amount A using as few coins as possible. Greedy fails here — with coins [1,5,6,9] and A = 11 greedy takes 9+1+1 = 3 coins, but 5+6 = 2 is optimal.

dp[i][0] = 0,   dp[0][a>0] = ∞
dp[i][a] = dp[i-1][a]                              if coin[i] > a
dp[i][a] = min( dp[i-1][a],  1 + dp[i][a-coin[i]] ) otherwise
                 skip coin      reuse the same coin (row i, not i-1)

Gold = answer. Blue = coins used on the traceback. Grey ∞ = unreachable.

int minCoins(const vector<int>& coins, int A) {
    const int INF = INT_MAX / 2;
    vector<int> dp(A + 1, INF);
    dp[0] = 0;
    for (int c : coins)                  // unbounded: amount ascends
        for (int a = c; a <= A; ++a)
            dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[A] >= INF ? -1 : dp[A];
}

Find the length of the longest strictly increasing subsequence of an array. Elements need not be adjacent, but must keep their original order.

dp[i] = 1 + max{ dp[j] : j < i and a[j] < a[i] }    (or 1 if no such j)
answer = max over all i of dp[i]     — not dp[n-1]

Gold = the maximum (the answer). Blue = the chain of predecessors forming that subsequence.

int lis(const vector<int>& a) {
    int n = a.size(), best = 0;
    vector<int> dp(n, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        best = max(best, dp[i]);
    }
    return best;
}

Given a chain of matrices, choose the parenthesisation that minimises the total number of scalar multiplications. Matrix sizes are given as a dimension array p, where matrix Aᵢ is p[i-1] × p[i].

m[i][i] = 0
m[i][j] = min over k in [i, j-1] of
          m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j]
Fill by increasing chain length L, not row by row.

Gold = full chain cost. The diagonal is 0 (a single matrix costs nothing).

Read s[1][4] = 1: split the chain after A₁, then recurse — s[2][4] = 3 splits after A₃.

int mcm(const vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> m(n + 1, vector<int>(n + 1, 0));
    for (int L = 2; L <= n; ++L)                    // chain length
        for (int i = 1; i + L - 1 <= n; ++i) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; ++k)
                m[i][j] = min(m[i][j],
                              m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
        }
    return m[1][n];
}

Given sorted keys and how often each is searched for, build the BST that minimises the total expected search cost — that is, Σ freq[k] × (depth of k + 1). Frequently searched keys want to sit near the root.

dp[i][i] = freq[i]
dp[i][j] = min over r in [i, j] of
          dp[i][r-1] + dp[r+1][j] + sum(freq[i..j])
The sum term appears because making key r the root pushes every
key in the range one level deeper, adding its frequency once.

Gold = full-range cost. Diagonal = a single key as its own root.

int optimalBST(const vector<int>& keys, const vector<int>& freq) {
    int n = keys.size();
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + freq[i];
    auto total = [&](int i, int j) { return pre[j+1] - pre[i]; };

    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = freq[i];
    for (int L = 2; L <= n; ++L)
        for (int i = 0; i + L - 1 < n; ++i) {
            int j = i + L - 1;
            dp[i][j] = INT_MAX;
            for (int r = i; r <= j; ++r) {
                int left  = (r > i) ? dp[i][r-1] : 0;
                int right = (r < j) ? dp[r+1][j] : 0;
                dp[i][j] = min(dp[i][j], left + right + total(i, j));
            }
        }
    return dp[0][n-1];
}

Find the length of the longest subsequence of a string that reads the same forwards and backwards. (Equivalently: the LCS of the string with its own reverse.)

dp[i][i] = 1
dp[i][j] = dp[i+1][j-1] + 2                if s[i] == s[j]
dp[i][j] = max( dp[i+1][j],  dp[i][j-1] )   otherwise
Fill by increasing substring length — dp[i][j] depends on shorter windows.

Gold = the whole string. Diagonal = 1 (a single character is a palindrome).

int lps(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = 1;
    for (int L = 2; L <= n; ++L)
        for (int i = 0; i + L - 1 < n; ++i) {
            int j = i + L - 1;
            if (s[i] == s[j]) dp[i][j] = (L > 2 ? dp[i+1][j-1] : 0) + 2;
            else              dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    return dp[0][n-1];
}

Decide whether a pattern matches a whole string, where '.' matches any single character and '*' means “zero or more of the preceding element”. The match must cover the entire string.

dp[0][0] = true
dp[i][0] = dp[i-2][0]   if p[i] == '*'   (a '*' group can match nothing)
if p[i] == '.' or p[i] == t[j]:   dp[i][j] = dp[i-1][j-1]
if p[i] == '*':   dp[i][j] = dp[i-2][j]                       (use zero copies)
                  OR  dp[i][j-1]  when p[i-1] matches t[j]     (use one more copy)
otherwise:   dp[i][j] = false

Green = matches, grey = does not. Gold = full pattern vs full text.

bool isMatch(const string& t, const string& p) {
    int n = t.size(), m = p.size();
    vector<vector<char>> dp(m + 1, vector<char>(n + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= m; ++i)
        if (p[i-1] == '*') dp[i][0] = dp[i-2][0];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            if (p[i-1] == '*') {
                bool same = (p[i-2] == '.' || p[i-2] == t[j-1]);
                dp[i][j] = dp[i-2][j] || (same && dp[i][j-1]);
            } else if (p[i-1] == '.' || p[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    return dp[m][n];
}

A rod of length N can be cut into integer-length pieces, and a piece of length i sells for price[i]. Choose the cuts that maximise total revenue. This is unbounded knapsack: each piece length can be used any number of times.

dp[i][0] = 0,  dp[0][L] = 0
dp[i][L] = dp[i-1][L]                                  if i > L
dp[i][L] = max( dp[i-1][L],  price[i] + dp[i][L-i] )    otherwise
                               same row i → reuse allowed

Gold = answer. Blue = pieces chosen on the traceback.

int rodCutting(const vector<int>& price, int N) {
    // price[i-1] is the price of a piece of length i
    vector<int> dp(N + 1, 0);
    for (int L = 1; L <= N; ++L)
        for (int i = 1; i <= min<int>(L, price.size()); ++i)
            dp[L] = max(dp[L], price[i-1] + dp[L - i]);
    return dp[N];
}

Each element of the array says the maximum number of steps you may jump forward from that position. Starting at index 0, reach the last index in as few jumps as possible.

dp[0] = 0
dp[i] = 1 + min{ dp[j] : j < i and j + a[j] ≥ i }
dp[i] = ∞ if no such j exists (index i is unreachable)

Gold = the last index. Blue = the chain of jumps that reaches it.

int minJumps(const vector<int>& a) {
    int n = a.size();
    const int INF = INT_MAX / 2;
    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (j + a[j] >= i) dp[i] = min(dp[i], dp[j] + 1);
    return dp[n-1] >= INF ? -1 : dp[n-1];
}

Each job has a start time, an end time and a profit. Pick a set of jobs that do not overlap in time so that total profit is maximised. Unlike the unweighted version, “earliest finishing time first” greedy is wrong once profits differ.

Sort jobs by end time. Let latest(i) = the largest index j < i with end[j] ≤ start[i].
dp[0] = profit[0]
dp[i] = max( dp[i-1],  profit[i] + dp[latest(i)] )
         skip job i     take it, then jump past all overlaps

Gold = final answer. Blue = jobs actually selected on the traceback.

struct Job { int start, end, profit; };

int jobScheduling(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end(),
         [](const Job& x, const Job& y) { return x.end < y.end; });
    int n = jobs.size();
    vector<int> ends(n), dp(n);
    for (int i = 0; i < n; ++i) ends[i] = jobs[i].end;

    dp[0] = jobs[0].profit;
    for (int i = 1; i < n; ++i) {
        // rightmost job whose end <= start of job i
        int k = int(upper_bound(ends.begin(), ends.begin() + i,
                                jobs[i].start) - ends.begin()) - 1;
        int incl = jobs[i].profit + (k >= 0 ? dp[k] : 0);
        dp[i] = max(dp[i-1], incl);
    }
    return dp[n-1];
}

Find the contiguous rectangular submatrix with the largest sum. The trick is to fix a pair of top and bottom rows, collapse those rows into a single array of column sums, and run 1D Kadane on it — turning a 2D search into R² runs of a linear scan.

for top in 0..R-1:
    acc = [0] * C
    for bot in top..R-1:
        acc[c] += M[bot][c]   for every column c
        best = max(best, kadane(acc))

Gold = the row pair that produced the global maximum.

int maxSumSubmatrix(const vector<vector<int>>& M) {
    int R = M.size(), C = M[0].size();
    int best = INT_MIN;
    for (int top = 0; top < R; ++top) {
        vector<int> acc(C, 0);
        for (int bot = top; bot < R; ++bot) {
            for (int c = 0; c < C; ++c) acc[c] += M[bot][c];
            int cur = 0;                    // Kadane on the collapsed strip
            for (int x : acc) {
                cur = (cur <= 0) ? x : cur + x;
                best = max(best, cur);
            }
        }
    }
    return best;
}

There is a floor T in a building such that an egg dropped from floor T or above breaks, and from below T it does not. With a given number of identical eggs, find the minimum number of drops that guarantees identifying T in the worst case.

dp[1][f] = f      (one egg → must test floor by floor from the bottom)
dp[e][0] = 0,  dp[e][1] = 1
dp[e][f] = 1 + min over k in [1, f] of
           max( dp[e-1][k-1],  dp[e][f-k] )
                egg breaks       egg survives
The max is the adversary picking the worse branch; the min is you picking the best floor k.

Gold = the answer. Row 1 is just the identity — with one egg you cannot do better than linear.

int eggDrop(int eggs, int floors) {
    vector<vector<int>> dp(eggs + 1, vector<int>(floors + 1, 0));
    for (int f = 0; f <= floors; ++f) dp[1][f] = f;
    for (int e = 2; e <= eggs; ++e)
        for (int f = 1; f <= floors; ++f) {
            dp[e][f] = INT_MAX;
            for (int k = 1; k <= f; ++k)
                dp[e][f] = min(dp[e][f], 1 + max(dp[e-1][k-1], dp[e][f-k]));
        }
    return dp[eggs][floors];
}

Find the longest run of characters that appears contiguously in both strings. Almost the same table as LCS, with one crucial difference: a mismatch resets the cell to 0 instead of inheriting a neighbour, because a substring cannot skip characters.

dp[i][j] = dp[i-1][j-1] + 1   if a[i] == b[j]
dp[i][j] = 0                  otherwise   ← the difference from LCS
answer = max cell in the whole table (not the bottom-right corner)

Gold = the maximum cell. Blue = the diagonal run leading into it.

int longestCommonSubstring(const string& a, const string& b) {
    int n = a.size(), m = b.size(), best = 0;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                best = max(best, dp[i][j]);
            }
            // else stays 0 -- the run is broken
    return best;
}

Given a string with no spaces and a dictionary, decide whether the string can be segmented into a sequence of dictionary words. The greedy “take the longest word “ approach fails, because an early long match can strand the rest of the string.

dp[0] = true   (the empty prefix)
dp[i] = OR over j in [0, i-1] of  ( dp[j]  AND  s[j..i-1] in dict )

Green = segmentable prefix, grey = not. Blue = the split points on one valid segmentation.

bool wordBreak(const string& s, const unordered_set<string>& dict) {
    int n = s.size();
    vector<char> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < i; ++j)
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
    return dp[n];
}

Count how many distinct combinations of coins add up to an amount. Combinations, not permutations — 1+2 and 2+1 count once. Adding coins one denomination at a time (outer loop over coins) is exactly what prevents double counting.

dp[i][0] = 1   (one way: use nothing),   dp[0][a>0] = 0
dp[i][a] = dp[i-1][a]  +  dp[i][a-coin[i]]
            ignore coin i     use coin i at least once

Gold = the answer. Column 0 is all 1s — there is exactly one way to make nothing.

long long countWays(const vector<int>& coins, int A) {
    vector<long long> dp(A + 1, 0);
    dp[0] = 1;
    for (int c : coins)          // coins outer => combinations, not permutations
        for (int a = c; a <= A; ++a)
            dp[a] += dp[a - c];
    return dp[A];
}

In a binary matrix, find the largest area rectangle containing only 1s. The insight: treat every row as the base of a histogram whose bar heights are the runs of 1s stacked above it, then solve “largest rectangle in a histogram” once per row.

h[r][c] = 0                 if M[r][c] == 0
h[r][c] = h[r-1][c] + 1     if M[r][c] == 1
answer = max over rows r of  largestRectangleInHistogram( h[r] )

Gold = the histogram bars that formed the winning rectangle.

int largestHistogram(const vector<int>& h) {
    int n = h.size(), best = 0;
    stack<int> st;
    for (int i = 0; i <= n; ++i) {
        int cur = (i < n) ? h[i] : 0;
        while (!st.empty() && h[st.top()] >= cur) {
            int top = st.top(); st.pop();
            int left = st.empty() ? 0 : st.top() + 1;
            best = max(best, h[top] * (i - left));
        }
        st.push(i);
    }
    return best;
}

int maximalRectangle(const vector<vector<int>>& M) {
    int R = M.size(), C = M[0].size(), best = 0;
    vector<int> h(C, 0);
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) h[c] = M[r][c] ? h[c] + 1 : 0;
        best = max(best, largestHistogram(h));
    }
    return best;
}

The same minimum-coin problem as #05, collapsed to a single array. Instead of a row per denomination, walk the amount from 1 upward and try every coin at each step. This is the form worth memorising — it is shorter, uses O(A) space, and generalises cleanly.

dp[0] = 0,  dp[a] = ∞ initially
dp[a] = 1 + min{ dp[a - c] : c in coins, c ≤ a }
Amounts are filled ascending, so dp[a-c] is always already final.

Gold = the answer. Blue = amounts visited on the traceback.

int minCoins(const vector<int>& coins, int A) {
    const int INF = INT_MAX / 2;
    vector<int> dp(A + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= A; ++a)
        for (int c : coins)
            if (c <= a && dp[a - c] + 1 < dp[a])
                dp[a] = dp[a - c] + 1;
    return dp[A] >= INF ? -1 : dp[A];
}

Given daily prices, make at most K buy-then-sell transactions (you must sell before buying again) to maximise profit. The naive recurrence scans all earlier days and costs O(K·n²); keeping a running maximum of (previous-transaction profit − price) makes it O(K·n).

dp[0][d] = 0,   dp[t][0] = 0
dp[t][d] = max( dp[t][d-1],                       ← do nothing on day d
                price[d] + max over m<d of ( dp[t-1][m] − price[m] ) )
The inner max is carried as a single running variable, so each cell is O(1).

Gold = the answer. Row 0 is all zeros: no transactions, no profit.

int maxProfit(const vector<int>& prices, int K) {
    int n = prices.size();
    if (n < 2) return 0;
    vector<vector<int>> dp(K + 1, vector<int>(n, 0));
    for (int t = 1; t <= K; ++t) {
        int best = -prices[0];        // max(dp[t-1][m] - prices[m]) so far
        for (int d = 1; d < n; ++d) {
            dp[t][d] = max(dp[t][d-1], prices[d] + best);
            best = max(best, dp[t-1][d] - prices[d]);
        }
    }
    return dp[K][n-1];
}

Glob-style matching: '?' matches exactly one character, '*' matches any sequence including the empty one. Simpler than regex matching (#10) because '*' stands alone rather than modifying the character before it.

dp[0][0] = true;   dp[i][0] = dp[i-1][0]  when p[i] == '*'
p[i] == '*':   dp[i][j] = dp[i-1][j]  OR  dp[i][j-1]
                          match empty     absorb one more character
p[i] == '?' or p[i] == t[j]:   dp[i][j] = dp[i-1][j-1]
otherwise:   dp[i][j] = false

Green = matches, grey = does not. Gold = full pattern vs full text.

bool isMatch(const string& t, const string& p) {
    int n = t.size(), m = p.size();
    vector<vector<char>> dp(m + 1, vector<char>(n + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= m; ++i)
        if (p[i-1] == '*') dp[i][0] = dp[i-1][0];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            if (p[i-1] == '*')
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            else if (p[i-1] == '?' || p[i-1] == t[j-1])
                dp[i][j] = dp[i-1][j-1];
        }
    return dp[m][n];
}

Break a paragraph into lines of at most L characters so that the total “badness” is minimised, where a line's badness is the square of its trailing whitespace. Squaring is what makes the algorithm spread slack evenly instead of dumping it all on one line — greedy line-filling does not.

extra = L − (sum of word lengths i..j) − (j − i)     ← the j−i single spaces
cost[i][j] = extra²  if extra ≥ 0,  else ∞
dp[0] = 0
dp[j] = min over i in [0, j-1] of  dp[i] + cost[i][j-1]

Blue = the three lines actually chosen. Grey ∞ = the words do not fit on one line.

Gold = the answer.

int justify(const vector<string>& words, int L) {
    int n = words.size();
    const int INF = INT_MAX / 2;
    vector<vector<int>> cost(n, vector<int>(n, INF));
    for (int i = 0; i < n; ++i) {
        int total = 0;
        for (int j = i; j < n; ++j) {
            total += words[j].size();
            int extra = L - total - (j - i);
            if (extra < 0) break;
            cost[i][j] = extra * extra;
        }
    }
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int j = 1; j <= n; ++j)
        for (int i = 0; i < j; ++i)
            if (cost[i][j-1] < INF)
                dp[j] = min(dp[j], dp[i] + cost[i][j-1]);
    return dp[n];
}

Every cell of a grid has a cost. Starting top-left and moving only right or down, reach the bottom-right cell as cheaply as possible. The purest grid DP there is — each cell needs only its neighbour above and its neighbour to the left.

dp[0][0] = M[0][0]
dp[0][j] = dp[0][j-1] + M[0][j]      ← top row: only from the left
dp[i][0] = dp[i-1][0] + M[i][0]      ← left column: only from above
dp[i][j] = M[i][j] + min( dp[i-1][j], dp[i][j-1] )

Gold = destination. Blue = the path recovered by walking back to the origin.

int minCostPath(const vector<vector<int>>& M) {
    int R = M.size(), C = M[0].size();
    vector<vector<int>> dp(R, vector<int>(C, 0));
    dp[0][0] = M[0][0];
    for (int j = 1; j < C; ++j) dp[0][j] = dp[0][j-1] + M[0][j];
    for (int i = 1; i < R; ++i) dp[i][0] = dp[i-1][0] + M[i][0];
    for (int i = 1; i < R; ++i)
        for (int j = 1; j < C; ++j)
            dp[i][j] = M[i][j] + min(dp[i-1][j], dp[i][j-1]);
    return dp[R-1][C-1];
}

Coins of different values lie in a row. Two players alternate, each taking a coin from either end. Both play optimally; how much can the first player guarantee? The subtlety is that after your move the opponent chooses, so you must assume the worse of their two replies — hence a min nested inside the max.

dp[i][i] = coins[i]
dp[i][j] = max(
   coins[i] + min( dp[i+2][j],  dp[i+1][j-1] ),   ← you take the left coin
   coins[j] + min( dp[i+1][j-1], dp[i][j-2] ) )   ← you take the right coin
The inner min is the opponent choosing the reply that is worst for you.

Gold = the whole row. Diagonal = a single coin, which the mover simply takes.

int optimalStrategy(const vector<int>& c) {
    int n = c.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = c[i];
    for (int L = 2; L <= n; ++L)
        for (int i = 0; i + L - 1 < n; ++i) {
            int j = i + L - 1;
            int a = (i + 2 <= j)     ? dp[i+2][j]   : 0;
            int b = (i + 1 <= j - 1) ? dp[i+1][j-1] : 0;
            int d = (i     <= j - 2) ? dp[i][j-2]   : 0;
            dp[i][j] = max(c[i] + min(a, b),      // take the left coin
                           c[j] + min(b, d));     // take the right coin
        }
    return dp[0][n-1];
}

Find the largest square (not rectangle) made entirely of 1s. A cell can be the bottom-right corner of a k×k square only if its top, left and top-left neighbours can each anchor a (k−1)×(k−1) square — so the recurrence is 1 + the minimum of three.

dp[i][j] = 0                     if M[i][j] == 0
dp[i][j] = 1                     if M[i][j] == 1 and i == 0 or j == 0
dp[i][j] = 1 + min( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )   otherwise
answer = max cell in the table

Gold = the maximum cell (bottom-right corner). Blue = the square it represents.

int maxSquare(const vector<vector<int>>& M) {
    int R = M.size(), C = M[0].size(), best = 0;
    vector<vector<int>> dp(R, vector<int>(C, 0));
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (M[i][j]) {
                dp[i][j] = (i == 0 || j == 0)
                         ? 1
                         : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                best = max(best, dp[i][j]);
            }
    return best;
}

Bursting balloon i earns left×i×right, where left and right are its current neighbours — so the array shrinks and the neighbours keep changing. The trick is to invert the question: instead of asking which balloon to burst first, ask which one to burst LAST in each open interval. That balloon's neighbours are then fixed at the interval edges, and the two sides become independent subproblems.

dp[i][j] = 0   when j ≤ i + 1  (nothing strictly between)
dp[i][j] = max over k in (i, j) of
           a[i]·a[k]·a[j]  +  dp[i][k]  +  dp[k][j]
k is the balloon burst LAST, which is why its neighbours are a[i] and a[j].

Gold = the full padded range. Cells with j ≤ i+1 are empty or zero: no balloons inside.

int maxCoins(const vector<int>& nums) {
    vector<int> a;
    a.push_back(1);
    a.insert(a.end(), nums.begin(), nums.end());
    a.push_back(1);

    int n = a.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int L = 2; L < n; ++L)                    // interval width
        for (int i = 0; i + L < n; ++i) {
            int j = i + L;
            for (int k = i + 1; k < j; ++k)
                dp[i][j] = max(dp[i][j],
                               a[i]*a[k]*a[j] + dp[i][k] + dp[k][j]);
        }
    return dp[0][n-1];
}

Cut a string into pieces so that every piece is a palindrome, using as few cuts as possible. Done in two stages: first a boolean table of which substrings are palindromes, then a linear pass that finds the cheapest place to make the last cut.

pal[i][i] = true
pal[i][j] = ( s[i] == s[j] )  AND  ( j − i < 2  OR  pal[i+1][j-1] )

cuts[j] = 0                                        if pal[0][j]
cuts[j] = min over i in [1, j] with pal[i][j] of  cuts[i-1] + 1

Green = palindrome. Note pal[1][5] is true, which is what makes one cut enough.

Gold = the answer.

int minCut(const string& s) {
    int n = s.size();
    vector<vector<char>> pal(n, vector<char>(n, false));
    for (int L = 1; L <= n; ++L)
        for (int i = 0; i + L - 1 < n; ++i) {
            int j = i + L - 1;
            pal[i][j] = (s[i] == s[j]) && (L < 3 || pal[i+1][j-1]);
        }
    vector<int> cuts(n, 0);
    for (int j = 0; j < n; ++j) {
        if (pal[0][j]) { cuts[j] = 0; continue; }
        cuts[j] = INT_MAX;
        for (int i = 1; i <= j; ++i)
            if (pal[i][j]) cuts[j] = min(cuts[j], cuts[i-1] + 1);
    }
    return cuts[n-1];
}

Stack 3D boxes to build the tallest tower, where a box may sit on another only if both base dimensions are strictly smaller. Boxes can be rotated and each may be used any number of times — but generating all three rotations up front and then forbidding repeats gives the same answer, since two identical bases can never stack.

Generate 3 rotations per box, normalise each base so width ≤ depth,
sort all rotations by base area descending.

dp[i] = height[i] + max{ dp[j] : j < i, width[j] > width[i], depth[j] > depth[i] }
answer = max over all i of dp[i]
This is Longest Increasing Subsequence with a 2D comparison and height as the weight.

Gold = the tallest tower. Blue = the boxes stacked in it, top of the list being lowest.

struct Box { int h, w, d; };

int boxStacking(const vector<Box>& boxes) {
    vector<Box> rot;
    for (const Box& b : boxes) {
        int t[3][3] = {{b.h, b.w, b.d}, {b.w, b.h, b.d}, {b.d, b.h, b.w}};
        for (auto& r : t)
            rot.push_back({r[0], min(r[1], r[2]), max(r[1], r[2])});
    }
    sort(rot.begin(), rot.end(), [](const Box& x, const Box& y) {
        return x.w * x.d > y.w * y.d;          // base area, descending
    });

    int n = rot.size(), best = 0;
    vector<int> dp(n);
    for (int i = 0; i < n; ++i) {
        dp[i] = rot[i].h;
        for (int j = 0; j < i; ++j)
            if (rot[j].w > rot[i].w && rot[j].d > rot[i].d)
                dp[i] = max(dp[i], dp[j] + rot[i].h);
        best = max(best, dp[i]);
    }
    return best;
}

Decide whether string c is formed by interleaving a and b — that is, whether c can be split into pieces alternating from a and b while preserving the order within each. Greedy character matching fails when both a and b offer the same next character.

dp[0][0] = true
dp[i][j] =  ( a[i] == c[i+j]  AND  dp[i-1][j] )
         OR ( b[j] == c[i+j]  AND  dp[i][j-1] )
Position in c is always i+j — no third index is needed.

Green = this prefix pair works. Gold = both strings fully consumed.

bool isInterleave(const string& a, const string& b, const string& c) {
    int n = a.size(), m = b.size();
    if (n + m != (int)c.size()) return false;
    vector<vector<char>> dp(n + 1, vector<char>(m + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            if (i && a[i-1] == c[i+j-1] && dp[i-1][j]) dp[i][j] = true;
            if (j && b[j-1] == c[i+j-1] && dp[i][j-1]) dp[i][j] = true;
        }
    return dp[n][m];
}

Count the distinct ways to climb n steps taking 1 or 2 steps at a time. The answer is the Fibonacci sequence, and this is the smallest problem that shows the whole DP idea: the last move was either a 1-step or a 2-step, so the counts simply add.

dp[0] = 1   (one way to stand at the bottom: do nothing)
dp[i] = dp[i-1] + dp[i-2]                     ← steps of 1 or 2
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]           ← steps of 1, 2 or 3

Gold = the answer for n = 10. Row 1 is Fibonacci; row 2 is the tribonacci sequence.

long long climb(int n, const vector<int>& steps = {1, 2}) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int s : steps)
            if (i - s >= 0) dp[i] += dp[i - s];
    return dp[n];
}

Pick a subset of array elements with the largest possible sum, subject to never picking two neighbours. Known elsewhere as the House Robber problem. At every index the choice is binary — skip it and inherit, or take it and jump back two.

dp[0] = max(0, a[0])
dp[1] = max( dp[0], a[1] )
dp[i] = max( dp[i-1],  dp[i-2] + a[i] )
         skip a[i]     take a[i]

Gold = the answer. Blue = the elements selected on the traceback.

int maxNonAdjacent(const vector<int>& a) {
    int incl = 0, excl = 0;   // best including / excluding the previous element
    for (int x : a) {
        int nextIncl = excl + x;
        excl = max(incl, excl);
        incl = nextIncl;
    }
    return max(incl, excl);
}

Given n distinct sorted keys, how many structurally different binary SEARCH trees can be built? Because the keys are sorted, choosing key r as the root forces the first r keys into the left subtree and the rest into the right — so only the counts matter, not the key values. The result is the Catalan numbers.

dp[0] = 1   (the empty tree)
dp[i] = Σ over r in [0, i-1] of   dp[r] · dp[i-1-r]
        r keys go left, i-1-r go right, one key is the root
Closed form: dp[n] = C(2n, n) / (n+1), the nth Catalan number.

Gold = the answer for n = 5. The sequence 1, 1, 2, 5, 14, 42, 132 is Catalan.

long long countBST(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int r = 0; r < i; ++r)
            dp[i] += dp[r] * dp[i - 1 - r];
    return dp[n];
}

Find the increasing subsequence with the largest SUM rather than the greatest length. Same scan as LIS (#06), but each cell accumulates values instead of counting elements — and the two answers often disagree, as they do here.

dp[i] = a[i]  initially
dp[i] = a[i] + max{ dp[j] : j < i and a[j] < a[i] }
answer = max over all i of dp[i]

Gold = the maximum. Blue = the subsequence achieving it.

int maxSumIncreasing(const vector<int>& a) {
    int n = a.size(), best = 0;
    vector<int> dp(a);                       // dp[i] starts at a[i]
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]);
        best = max(best, dp[i]);
    }
    return best;
}

Count the distinct paths from the top-left cell to the bottom-right cell of a grid when only right and down moves are allowed. Every cell is reached from exactly two places, so the counts simply add — the table is Pascal's triangle laid on its side.

dp[0][j] = dp[i][0] = 1   (one straight path along each edge)
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Closed form: C(R+C-2, R-1).

Gold = the destination.

long long countPaths(int R, int C) {
    vector<vector<long long>> dp(R, vector<long long>(C, 1));
    for (int i = 1; i < R; ++i)
        for (int j = 1; j < C; ++j)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[R-1][C-1];
}

The identical problem to #01, solved by writing the recursion directly and caching results. The point of this table is what is MISSING: bottom-up fills all 40 cells, while memoisation only ever computes the 10 states the recursion actually reaches. When the reachable state space is sparse, top-down wins; when it is dense, bottom-up wins on constant factors and needs no recursion stack.

solve(0, c) = solve(i, 0) = 0
solve(i, c) = solve(i-1, c)                                   if w[i] > c
solve(i, c) = max( solve(i-1, c), v[i] + solve(i-1, c-w[i]) )  otherwise
Identical maths to #01 — only the evaluation order differs.

Gold = the top-level call. Blue = states actually computed. Grey · = never touched.

int knapsackTopDown(const vector<int>& w, const vector<int>& v, int W) {
    int n = w.size();
    vector<vector<int>> memo(n + 1, vector<int>(W + 1, -1));

    function<int(int, int)> solve = [&](int i, int c) -> int {
        if (i == 0 || c == 0) return 0;
        int& cached = memo[i][c];
        if (cached != -1) return cached;

        int best = solve(i - 1, c);
        if (w[i-1] <= c)
            best = max(best, v[i-1] + solve(i - 1, c - w[i-1]));
        return cached = best;
    };
    return solve(n, W);
}

Find the longest subsequence that first increases and then decreases. Rather than a new recurrence, run LIS twice — once forward, once backward — and for each index add the two lengths, subtracting 1 because the peak element is counted in both.

inc[i] = 1 + max{ inc[j] : j < i, a[j] < a[i] }      ← left-to-right pass
dec[i] = 1 + max{ dec[j] : j > i, a[j] < a[i] }      ← right-to-left pass
answer = max over i of  inc[i] + dec[i] − 1
Index i is the peak; subtract 1 so it is not double counted.

Gold = the best peak. Read the last row as “longest bitonic subsequence peaking here”.

int longestBitonic(const vector<int>& a) {
    int n = a.size();
    vector<int> inc(n, 1), dec(n, 1);
    for (int i = 0; i < n; ++i)                    // left-to-right LIS
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) inc[i] = max(inc[i], inc[j] + 1);
    for (int i = n - 1; i >= 0; --i)               // right-to-left LIS
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[i]) dec[i] = max(dec[i], dec[j] + 1);

    int best = 0;
    for (int i = 0; i < n; ++i) best = max(best, inc[i] + dec[i] - 1);
    return best;
}

Count binary strings of length n that never contain two adjacent 1s. The move that makes it easy is splitting the count by what the string ENDS with: a string ending in 0 can be extended either way, but a string ending in 1 can only be extended with a 0.

zero[1] = 1,  ones[1] = 1
zero[i] = zero[i-1] + ones[i-1]     ← appending 0 is always safe
ones[i] = zero[i-1]                 ← appending 1 needs a 0 before it
answer = zero[n] + ones[n]  =  Fibonacci(n+2)

Gold = the answer for n = 5. Each row is a shifted Fibonacci sequence.

long long countNoConsecutiveOnes(int n) {
    long long zero = 1, ones = 1;      // length-1 strings: "0" and "1"
    for (int i = 2; i <= n; ++i) {
        long long z = zero + ones;     // appending 0 is always safe
        long long o = zero;            // appending 1 needs a 0 before it
        zero = z;
        ones = o;
    }
    return zero + ones;
}

Answer many “sum of this rectangle” queries on a matrix that never changes. Precompute a prefix-sum table once in O(R·C), then every query is four lookups — the two overlapping strips get subtracted, so the corner they share is added back. Inclusion–exclusion in two dimensions.

S[i][j] = M[i-1][j-1] + S[i-1][j] + S[i][j-1] − S[i-1][j-1]

query(r1, c1, r2, c2) =
   S[r2+1][c2+1] − S[r1][c2+1] − S[r2+1][c1] + S[r1][c1]

Gold = the big rectangle. Blue = the three correction terms. Grey = the zero padding.

class NumMatrix {
    vector<vector<int>> S;
public:
    explicit NumMatrix(const vector<vector<int>>& M) {
        int R = M.size(), C = M[0].size();
        S.assign(R + 1, vector<int>(C + 1, 0));
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                S[i][j] = M[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
    }

    int sumRegion(int r1, int c1, int r2, int c2) const {
        return S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1];
    }
};

The minimum-coin problem again, written as plain recursion with a cache. Compare with #05 and #20: the recurrence is unchanged, but evaluation starts at the target amount and descends. Here every amount happens to be reachable, so the memo fills completely — with large denominations and a large target, most of it would stay empty.

solve(0) = 0
solve(a) = 1 + min{ solve(a − c) : c in coins, c ≤ a }
Called top-down from a = A; each distinct amount is solved once.

Gold = the top-level call. Blue = amounts computed and cached.

int minCoinsTopDown(const vector<int>& coins, int A) {
    const int INF = INT_MAX / 2;
    vector<int> memo(A + 1, -1);

    function<int(int)> solve = [&](int a) -> int {
        if (a == 0) return 0;
        int& cached = memo[a];
        if (cached != -1) return cached;

        int best = INF;
        for (int c : coins)
            if (c <= a) best = min(best, solve(a - c) + 1);
        return cached = best;
    };

    int r = solve(A);
    return r >= INF ? -1 : r;
}

In a grid of X and O, find the largest square whose BORDER is entirely X — the inside may be anything. Two precomputed tables make each candidate check O(1): how far X extends to the right of a cell, and how far it extends downward.

hor[i][j] = 0 if grid[i][j] == 'O',  else 1 + hor[i][j+1]
ver[i][j] = 0 if grid[i][j] == 'O',  else 1 + ver[i+1][j]

For each top-left corner (i, j), try side k from min(hor, ver) downward:
   valid if  hor[i+k-1][j] ≥ k   (bottom edge)
        and  ver[i][j+k-1] ≥ k   (right edge)
The top and left edges are already guaranteed by hor[i][j] and ver[i][j].

Blue = the winning top-left corner.

Blue = the same corner. Both must be ≥ the side length.

int maxXSquare(const vector<string>& g) {
    int R = g.size(), C = g[0].size();
    vector<vector<int>> hor(R, vector<int>(C, 0)), ver(R, vector<int>(C, 0));
    for (int i = R - 1; i >= 0; --i)
        for (int j = C - 1; j >= 0; --j)
            if (g[i][j] == 'X') {
                hor[i][j] = 1 + (j + 1 < C ? hor[i][j+1] : 0);
                ver[i][j] = 1 + (i + 1 < R ? ver[i+1][j] : 0);
            }

    int best = 0;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            for (int k = min(hor[i][j], ver[i][j]); k > best; --k)
                if (hor[i+k-1][j] >= k && ver[i][j+k-1] >= k) {
                    best = k;                 // bottom and right edges hold
                    break;
                }
    return best;
}

Given only the LENGTH of a preorder traversal — not the values — count how many distinct binary trees could have produced it. In preorder the first element is the root and the remaining n−1 elements split into a left block and a right block, so the count depends only on the sizes. Same Catalan recurrence as #33, arrived at from a different direction.

dp[0] = 1   (the empty tree)
dp[i] = Σ over r in [0, i-1] of   dp[r] · dp[i-1-r]
        r nodes to the left of the root, i-1-r to the right
Identical to #33 — for unlabelled shapes, “how many BSTs on sorted keys” and
“how many binary trees on n nodes” are the same question.

Gold = the answer for n = 5. Compare with problem #33 — identical numbers.

long long countTrees(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int r = 0; r < i; ++r)
            dp[i] += dp[r] * dp[i - 1 - r];
    return dp[n];
}