Dynamic Programming Pattern

Last one in this run-through, and I’ll just say it up front: my DP folder in LeetCodePatterns is still public class Class1 { }. Nothing solved there yet. Every other pattern in this series got written up from code I’d actually pushed; this one’s the opposite order — I’m writing up the idea first because it’s too important to skip, and the first real solved problem will get dropped into that folder (and probably its own follow-up post) later.

What the pattern actually is

Dynamic programming is what you reach for when a problem has two properties at once:

• overlapping subproblems — solving it recursively means you’d solve the exact same smaller subproblem over and over, and
• optimal substructure — the answer to the big problem can be built directly out of answers to those smaller subproblems.

If both hold, plain recursion is wasteful (often exponential) because it keeps redoing work it already did. DP just adds a memory: solve each distinct subproblem once, store the answer, and look it up instead of recomputing it. That’s the entire trick. There are two equivalent ways to apply it:

• top-down (memoization) — write the recursive solution the “naive” way, then wrap it with a cache (dictionary or array) keyed by the subproblem’s parameters. First call computes and stores; every repeat call is a lookup.
• bottom-up (tabulation) — figure out the order subproblems depend on each other, and fill a table from the smallest subproblem up to the one you actually want, so every value you need is already sitting in the table by the time you need it.

Same idea, different direction. Top-down reads closer to the recursive definition; bottom-up avoids recursion overhead and is usually what you want once you can see the dependency order clearly.

The problem

Since I don’t have a real solved one in the repo yet, here’s the smallest example that still shows the whole pattern honestly: Climbing Stairs, LeetCode 70.

You’re climbing a staircase with n steps. Each move you can go up either 1 step or 2 steps. How many distinct ways are there to reach the top?

For n = 3 there are 3 ways: 1+1+1, 1+2, 2+1. For n = 4 there are 5. Small numbers, but the growth is exactly Fibonacci, and that’s the point — it’s the cleanest possible illustration of “reuse subproblem answers instead of recomputing them.”

Finding the recurrence. Think about the very last move to reach step n. It was either a 1-step move from step n-1, or a 2-step move from step n-2 — those are the only two options, and they’re mutually exclusive, so every way to reach n is either “a way to reach n-1, then +1” or “a way to reach n-2, then +2”:

ways(n) = ways(n-1) + ways(n-2)

Base cases: ways(0) = 1 (there’s exactly one way to be already at the top — take zero steps) and ways(1) = 1 (only one move possible). Everything else follows the recurrence. Notice this is the overlapping-subproblems part in action: computing ways(5) naively needs ways(4) and ways(3), but ways(4) also needs ways(3) — recompute it recursively without caching and you’re re-deriving the same smaller answers exponentially many times.

Code

A small bottom-up version — my own for this post, not pulled from the repo since there’s nothing there yet:

public static int ClimbStairs(int n)
{
    if (n <= 1) return 1;

    int prev2 = 1; // ways(0)
    int prev1 = 1; // ways(1)

    for (int i = 2; i <= n; i++)
    {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

This is the “you don’t actually need the whole table” upgrade on top of tabulation: since ways(i) only ever depends on the two values right before it, you don’t need to keep an array of all n values around — just the last two. O(n) time, O(1) space. The visualization below still draws the full table, though, because seeing all the intermediate values side by side is what makes the pattern click.

Try it

Bottom-up table for n = 8. At each step, the two cells being summed (dp[i-1] and dp[i-2]) light up amber, the cell about to be written lights up blue, then turns green once it’s finalized. Step through it or hit play.

Amber = the two previous values being summed. Blue = the cell being written. Green = finalized.

How to spot this pattern

The phrasing is usually the giveaway: “count the number of ways to…”, “find the min/max cost to…”, “can you reach/make X”, combined with a small set of choices at each step whose consequences overlap (like the 1-step-or-2-step choice above, or coin denominations, or take-or-skip). If recursion on the problem would naturally call itself with the same arguments more than once, it’s DP-shaped — memoize it top-down, or find the fill order and tabulate it bottom-up.

Once I actually solve a real DP problem in the repo, it’ll land in that empty folder and get its own follow-up post here.