// Dynamic Programming Basics

core idea

Every DP problem is four decisions, made in order: what’s the state (the minimal set of parameters that pins down a subproblem), what’s the recurrence (how a state’s answer is built from smaller states’ answers), what’s the base case (the states you can answer without recursing), and what’s the order (fill states so every dependency is already known when you need it). Two ways to run the same recurrence once you’ve named all four:

when to reach for it

• The problem asks to count the ways, or find a minimum/maximum cost or value, over a sequence of choices.
• A brute-force recursion would work but is exponential — and tracing it shows the same arguments being recomputed over and over.
• The problem has optimal substructure: the best answer for the whole input is built from the best answers to smaller versions of the same problem, not just any answer to them.
• You can name the state in a sentence (“the best score up to index i”, “the fewest coins to make amount a”) and that sentence has few enough distinct fillings to be practical — usually a polynomial count.

universal templates

Top-down (memoization) — write the recursion you’d write anyway, then cache it:

public int TopDown(int state, Dictionary<int, int> memo)
{
    if (IsBaseCase(state)) return BaseValue(state);
    if (memo.TryGetValue(state, out var cached)) return cached;

    int result = Recurrence(state);    // combines TopDown(smaller states)
    memo[state] = result;
    return result;
}

Bottom-up (tabulation) — the same recurrence, run forward through every state in dependency order:

public int BottomUp(int n)
{
    var dp = new int[n + 1];
    dp[0] = BaseValue;                 // seed the base case(s)

    for (int i = 1; i <= n; i++)
        dp[i] = Recurrence(dp, i);     // only reads already-filled entries

    return dp[n];
}

Every problem below names its state, writes the recurrence, and picks a direction. Most people think top-down first and ship bottom-up — the array is usually smaller than the recursion’s call stack, and there’s no depth limit to worry about.

problems

1. 01Climbing StairseasyLC #70

   Fibonacci in disguise — the "ways to reach i" recurrence.

2. 02House RobbermediumLC #198

   Take-or-skip: dp[i] = max(dp[i-1], dp[i-2] + a[i]).

3. 03Unique PathsmediumLC #62

   2D grid DP: cell = sum of the two ways in; rows compress to 1D.

4. 04Coin ChangemediumLC #322

   Min-coins per amount, built bottom-up — the unbounded knapsack shape.

5. 05Word BreakmediumLC #139

   DP over string prefixes, with a word set doing the lookups.

6. 06Longest Increasing SubsequencemediumLC #300

   O(n²) DP first; the O(n log n) patience upgrade as an optional coda.