DP foundations & 1D tables

Overlapping subproblems, memoization vs tabulation, and 1D DP on climbing stairs and coin change. · 11 min read

Concept

Dynamic programming applies when a problem has two traits: optimal substructure (the best answer is built from best answers to subproblems) and overlapping subproblems (the same subproblems recur). Instead of recomputing them, we solve each subproblem once and store the result.

Naive recursion for Fibonacci is O(2ⁿ) because fib(n-2) is recomputed all over the tree. DP collapses that to O(n) by remembering each value.

Memoization vs tabulation

• Memoization (top-down): write the natural recursion, but cache each result the first time you compute it.
• Tabulation (bottom-up): define a table dp[...], fill the base cases, then iterate in an order where every value's dependencies are already filled.

Both are O(states × work-per-state). Tabulation avoids recursion overhead and makes the fill order explicit — which is what the visualizer shows.

1D DP: climbing stairs

Ways to reach step i taking 1 or 2 steps: dp[i] = dp[i-1] + dp[i-2]. One dimension (the step index), constant work per state.

int climb(int n) {
    long long a = 1, b = 1;       // dp[i-2], dp[i-1]
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    return a;
}

1D DP: coin change

dp[a] = fewest coins to make amount a. For every amount, try each coin: dp[a] = min(dp[a], dp[a - c] + 1). Watch the 1D table fill:

Interactive visualization: Coin change — a 1D table over amounts — step through it frame by frame on this page.

Practice: Climbing Stairs (Easy) — How many ways to climb n stairs taking 1 or 2 steps? (1D DP)

Practice: Coin Change (Medium) — Fewest coins to make an amount (1D DP over amounts).