Dynamic Programming: State, Recurrence, Base Case, Order

Problem Context

Dynamic programming is the technique that turns "exponential and infeasible" into "polynomial and shippable". It's also the topic that produces more confused interview answers than any other, because every textbook teaches it bottom-up-first as if it were a black art. It isn't. DP is just memoized recursion with the recursion removed.

Two ingredients identify a DP problem: optimal substructure (the answer to the whole problem is built from answers to subproblems) and overlapping subproblems (those subproblems are solved many times). Once you spot both, the recipe is mechanical: write the recurrence, memoize, then (optionally) convert to a table for the constant-factor win and the smaller memory footprint.

Concept Explanation

The four-step DP recipe:

• 1. State — what parameters uniquely identify a subproblem? (e.g., dp[i][j] = min cost to convert first i chars to first j chars).
• 2. Recurrence — express dp[state] in terms of smaller states.
• 3. Base case — what are the smallest states whose answer is trivial?
• 4. Order — in what order do you fill the table so dependencies are computed first?

flowchart LR
    P["Problem looks recursive?"] --> O{"Optimal substructure?"}
    O -->|no| GREEDY["Try greedy or<br/>divide-and-conquer"]
    O -->|yes| OV{"Overlapping<br/>subproblems?"}
    OV -->|no| DC["Divide-and-conquer<br/>(no DP needed)"]
    OV -->|yes| TOP["Top-down:<br/>recursion + memo"]
    TOP --> CV{"Stack-safe and<br/>fast enough?"}
    CV -->|yes| DONE["Ship it"]
    CV -->|no| BOT["Convert to bottom-up<br/>+ space optimize"]

    style TOP fill:#0078D4,color:#fff,stroke:#005a9e
    style BOT fill:#16a34a,color:#fff,stroke:#15803d

Implementation

Step 1: Coin change — top-down memoization (the natural form)

// Min coins to make 'amount'; -1 if impossible
public static int CoinChange(int[] coins, int amount)
{
    var memo = new int?[amount + 1];
    int Solve(int rem)
    {
        if (rem == 0) return 0;
        if (rem < 0)  return int.MaxValue;
        if (memo[rem] is int v) return v;
        int best = int.MaxValue;
        foreach (var c in coins)
        {
            int sub = Solve(rem - c);
            if (sub != int.MaxValue) best = Math.Min(best, sub + 1);
        }
        return (int)(memo[rem] = best);
    }
    int ans = Solve(amount);
    return ans == int.MaxValue ? -1 : ans;
}

Step 2: Same problem — bottom-up table (constant-factor faster)

public static int CoinChangeBU(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 c in coins)
            if (c <= i) dp[i] = Math.Min(dp[i], dp[i - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

Step 3: 0/1 knapsack — 2D state, then space-optimize to 1D

// dp[i][w] = max value using first i items, capacity w
public static int Knapsack01(int[] wt, int[] val, int W)
{
    int n = wt.Length;
    var dp = new int[W + 1];                    // 1D — "current row" only
    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)        // ← iterate W down to avoid
            dp[w] = Math.Max(dp[w], dp[w - wt[i]] + val[i]);  // reusing item i
    return dp[W];
}
// Reverse iteration on w is the standard trick for 0/1 — forward iteration
// would let you take the same item multiple times (that&apos;s unbounded knapsack)

Step 4: Edit distance — the canonical 2D DP

public static int EditDistance(string s, string t)
{
    int n = s.Length, m = t.Length;
    var dp = new int[n + 1, m + 1];
    for (int i = 0; i <= n; i++) dp[i, 0] = i;          // delete all of s
    for (int j = 0; j <= m; j++) dp[0, j] = j;          // insert all of t
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i, j] = s[i - 1] == t[j - 1]
                ? dp[i - 1, j - 1]                       // match: free
                : 1 + Math.Min(dp[i - 1, j - 1],         // substitute
                      Math.Min(dp[i - 1, j], dp[i, j - 1])); // delete / insert
    return dp[n, m];
}

Step 5: LIS in O(n log n) — DP + binary search

// Longest Increasing Subsequence — beats O(n²) DP using patience sorting
public static int LIS(int[] a)
{
    var tails = new List<int>();   // tails[k] = smallest tail of any increasing
    foreach (var x in a)            //            subsequence of length k+1
    {
        int idx = tails.BinarySearch(x);
        if (idx < 0) idx = ~idx;
        if (idx == tails.Count) tails.Add(x);
        else                    tails[idx] = x;
    }
    return tails.Count;
}

Step 6: Reconstruct the solution, not just its cost

// LCS: build the table, then walk backwards from dp[n,m] to recover the sequence
public static string LCS(string s, string t)
{
    int n = s.Length, m = t.Length;
    var dp = new int[n + 1, m + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i, j] = s[i - 1] == t[j - 1]
                ? dp[i - 1, j - 1] + 1
                : Math.Max(dp[i - 1, j], dp[i, j - 1]);
    // reconstruct
    var sb = new System.Text.StringBuilder();
    for (int i = n, j = m; i > 0 && j > 0;)
    {
        if (s[i - 1] == t[j - 1]) { sb.Insert(0, s[i - 1]); i--; j--; }
        else if (dp[i - 1, j] >= dp[i, j - 1]) i--;
        else                                   j--;
    }
    return sb.ToString();
}

Pitfalls

1. State that doesn't uniquely identify a subproblem.If two different paths to the same "state" produce different optimal answers, your state is incomplete. Add the missing dimension (e.g., previous element, remaining capacity, last operation).

2. Wrong iteration order. When you use a 1D array for 0/1 knapsack, iterating w forward lets you reuse the same item multiple times, silently producing the unbounded-knapsack answer. Iterate downward.

3. Top-down on deep inputs blows the stack. Memoized recursion has the same depth as the recurrence. Forn = 100,000states with chain-shaped dependencies, you'll OOM the stack. Convert to bottom-up.

4. Memoizing on mutable state. If your memo key includes a list or object, equality and hashing surprise you. Use immutable keys (tuples of primitives, ImmutableArray) or encode state as integers.

5. Forgetting the base case for impossible states.Missing "return infinity for invalid" meansMath.Min picks the wrong branch and you get garbage answers. Be explicit about sentinels.

6. Greedy when you should DP (and vice versa). Greedy works for some coin systems (US coins) and fails for others (1, 3, 4 — needs DP). When in doubt, DP is safe; greedy is faster but requires a proof of optimality.

Practical Takeaways

• Always start top-down (recursion + memo). It's the natural translation of the recurrence.
• Convert to bottom-up only when stack depth, allocation, or constant-factor performance demands it.
• Space-optimize last — most 2D DPs collapse to 1D when the recurrence only references the previous row.
• State the four pieces aloud: state, recurrence, base case, order. If you can't, you don't have a solution yet.
• For 0/1 knapsack with 1D, iterate the capacity downward. For unbounded, iterate upward.
• To reconstruct the solution, store the table (not just the answer) and walk it backwards from the final cell.
• Some classics have better non-DP algorithms: LIS in O(n log n) via binary search beats the O(n²) DP.