Dynamic programming: 1D

coreCommon atGoogleAmazonMetaMicrosoftRead firstRecursionMemoizationPractise in the Sandbox →

Dynamic programming (DP) solves a problem by solving smaller versions of the same problem once each and storing the results. In 1-D DP the smaller versions are prefixes (or suffixes) of a sequence: dp[i] depends on a few earlier cells. Fill the table in order and the answer sits in the last cell. Typical cost: O(n · k) time for k choices per step, often O(1) space.

The idea in plain words

How many ways can you climb 7 stairs taking 1 or 2 at a time? Don’t list them. Think about the last move: you arrived at stair 7 from stair 6 (a 1-step) or from stair 5 (a 2-step). So

ways(7) = ways(6) + ways(5).

The same sentence applies to every stair. That self-similarity is the whole game. Two conditions make DP work:

• Optimal substructure. The answer for i can be built from answers for smaller inputs.
• Overlapping subproblems. Those smaller answers are needed many times. Plain recursion recomputes them (exponentially often); DP computes each once.

DP is “recursion + a table”. Top-down fills the table lazily (memoization); bottom-up fills it in order with a loop, which is what this page shows.

The 5-step recipe

Every DP solution, in an interview or not, comes from five decisions. Say them in this order:

Step	Question	Stairs example
1. State	What does dp[i] mean, in one sentence?	number of ways to land exactly on stair i
2. Transition	How does dp[i] follow from smaller states?	dp[i] = dp[i−1] + dp[i−2]
3. Base cases	Which states need no transition?	dp[0] = 1 (one way to make no moves)
4. Order	In what order are dependencies ready?	i = 1, 2, …, n
5. Answer	Which cell (or combination) is the result?	dp[n]

If you can’t write step 1 as a precise sentence, stop. Everything else follows from it.

See it

Each arrow points from a cell that dp[i] reads to dp[i] itself. In “count ways” try step sizes 1, 3, 5. In “min cost”, the dim arrow is the option that lost; at the end the route is recovered by following winners back.

Filling a 1-D DP table

step through

Count ways (climb stairs)Min cost (stairs with fees)

n (≤ 14)step sizes

n7

steps1,2

1 · state

dp[i] = # ways to reach step i

2 · transition

dp[i] = Σ dp[i − s]

3 · base

dp[0] = 1 (stand still)

4 · order

i = 1, 2, …, n

5 · answer

dp[n]

cell being filledcells it readsrecovered route

State first: dp[i] = number of distinct move sequences that land exactly on step i. Every other decision follows from this sentence.

↺◀▶ Play▶1 / 10

When to reach for it

The problem says…	Why 1-D DP fits
“how many ways to…” reach / build / tile something step by step	Counting: sum over the last choice.
“minimum cost / maximum value” over a sequence of decisions	Optimisation: min/max over the last choice.
“can you reach / is it possible…”	Feasibility: OR over the last choice.
each decision only looks back a bounded distance (1, 2, k steps)	dp[i] reads a fixed window of earlier cells.
brute force is “try every subset/path” with obvious repeats	Overlapping subproblems: the table removes the repeats.
a greedy idea has a small counterexample	DP considers every last choice instead of one. See greedy.

How it works

1. State. Write dp[i] = … as a sentence about a prefix (or about “ending at i”).
2. Transition. Ask “what was the last decision?” and combine the states it came from: + for counting, min/max for optimising, or for feasibility.
3. Base cases. Fill the cells the transition can’t reach (dp[0], sometimes dp[1]). Check them on the smallest input.
4. Order. Loop so every cell is computed after the cells it reads. For “reads earlier cells”, left to right.
5. Answer. Return the right cell, then see if you only ever read the last few cells: if so, keep only those (rolling variables).

Counting with a set of step sizes. The numbered comments match the recipe.

Python

count_ways.py

def count_ways(n: int, steps: list[int]) -> int:
    """Number of move sequences that climb exactly n stairs using the given step sizes."""
    # 1. state: ways[i] = number of sequences that land exactly on stair i
    ways = [0] * (n + 1)
    ways[0] = 1                               # 3. base: one way to stand still
    for i in range(1, n + 1):                 # 4. order: smaller i first
        # 2. transition: the last move was some s, from stair i - s
        ways[i] = sum(ways[i - s] for s in steps if s <= i)
    return ways[n]                            # 5. answer


if __name__ == "__main__":
    assert count_ways(7, [1, 2]) == 21        # Fibonacci in disguise
    assert count_ways(4, [1, 3]) == 3         # 1111, 13, 31
    assert count_ways(0, [1, 2]) == 1
    assert count_ways(5, [2]) == 0            # odd stairs, even steps
    print("ok")

TypeScript

count_ways.ts

import assert from "node:assert/strict";

/** Number of move sequences that climb exactly n stairs using the given step sizes. */
export function countWays(n: number, steps: number[]): number {
  // 1. state: ways[i] = number of sequences that land exactly on stair i
  const ways = new Array<number>(n + 1).fill(0);
  ways[0] = 1; // 3. base: one way to stand still
  for (let i = 1; i <= n; i++) { // 4. order: smaller i first
    for (const s of steps) {
      if (s <= i) ways[i] += ways[i - s]; // 2. transition: the last move was s, from stair i - s
    }
  }
  return ways[n]; // 5. answer
}

assert.equal(countWays(7, [1, 2]), 21); // Fibonacci in disguise
assert.equal(countWays(4, [1, 3]), 3); // 1111, 13, 31
assert.equal(countWays(0, [1, 2]), 1);
assert.equal(countWays(5, [2]), 0); // odd stairs, even steps
console.log("ok");

C#

count_ways.cs

// Number of move sequences that climb exactly n stairs using the given step sizes.
static long CountWays(int n, int[] steps)
{
    // 1. state: ways[i] = number of sequences that land exactly on stair i
    var ways = new long[n + 1];
    ways[0] = 1;                                // 3. base: one way to stand still
    for (int i = 1; i <= n; i++)                // 4. order: smaller i first
        foreach (int s in steps)
            if (s <= i) ways[i] += ways[i - s]; // 2. transition: the last move was s, from i - s
    return ways[n];                             // 5. answer
}

if (CountWays(7, [1, 2]) != 21) throw new Exception("expected 21");
if (CountWays(4, [1, 3]) != 3) throw new Exception("expected 3");
if (CountWays(0, [1, 2]) != 1) throw new Exception("expected 1");
if (CountWays(5, [2]) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Minimising, with the table collapsed to two variables because dp[i] only reads dp[i−1] and dp[i−2].

Python

min_cost_to_top.py

def min_cost_to_top(fee: list[int]) -> int:
    """Stepping off stair i costs fee[i]; move 1 or 2 stairs; start on stair 0 or 1 for free.
    Return the cheapest way to reach the top (one past the last stair)."""
    # 1. state: cost to be standing on stair i. 3. base: stairs 0 and 1 are free.
    two_back, one_back = 0, 0                    # cost[i-2], cost[i-1]
    for i in range(2, len(fee) + 1):             # 4. order: left to right
        # 2. transition: arrive from i-1 (pay fee[i-1]) or from i-2 (pay fee[i-2])
        here = min(one_back + fee[i - 1], two_back + fee[i - 2])
        two_back, one_back = one_back, here      # only the last two values are ever read
    return one_back                              # 5. answer: cost of standing on the top


if __name__ == "__main__":
    assert min_cost_to_top([10, 15, 20]) == 15
    assert min_cost_to_top([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) == 6
    assert min_cost_to_top([5, 7]) == 5
    print("ok")

TypeScript

min_cost_to_top.ts

import assert from "node:assert/strict";

/**
 * Stepping off stair i costs fee[i]; move 1 or 2 stairs; start on stair 0 or 1 for free.
 * Return the cheapest way to reach the top (one past the last stair).
 */
export function minCostToTop(fee: number[]): number {
  // 1. state: cost to be standing on stair i. 3. base: stairs 0 and 1 are free.
  let twoBack = 0, oneBack = 0; // cost[i-2], cost[i-1]
  for (let i = 2; i <= fee.length; i++) { // 4. order: left to right
    // 2. transition: arrive from i-1 (pay fee[i-1]) or from i-2 (pay fee[i-2])
    const here = Math.min(oneBack + fee[i - 1], twoBack + fee[i - 2]);
    [twoBack, oneBack] = [oneBack, here]; // only the last two values are ever read
  }
  return oneBack; // 5. answer: cost of standing on the top
}

assert.equal(minCostToTop([10, 15, 20]), 15);
assert.equal(minCostToTop([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]), 6);
assert.equal(minCostToTop([5, 7]), 5);
console.log("ok");

C#

min_cost_to_top.cs

// Stepping off stair i costs fee[i]; move 1 or 2 stairs; start on stair 0 or 1 for free.
// Return the cheapest way to reach the top (one past the last stair).
static int MinCostToTop(int[] fee)
{
    // 1. state: cost to be standing on stair i. 3. base: stairs 0 and 1 are free.
    int twoBack = 0, oneBack = 0;               // cost[i-2], cost[i-1]
    for (int i = 2; i <= fee.Length; i++)       // 4. order: left to right
    {
        // 2. transition: arrive from i-1 (pay fee[i-1]) or from i-2 (pay fee[i-2])
        int here = Math.Min(oneBack + fee[i - 1], twoBack + fee[i - 2]);
        (twoBack, oneBack) = (oneBack, here);   // only the last two values are ever read
    }
    return oneBack;                             // 5. answer: cost of standing on the top
}

if (MinCostToTop([10, 15, 20]) != 15) throw new Exception("expected 15");
if (MinCostToTop([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) != 6) throw new Exception("expected 6");
if (MinCostToTop([5, 7]) != 5) throw new Exception("expected 5");
Console.WriteLine("ok");

State as 'ending at i' vs 'using the first i'

Two flavours come up constantly. “Best answer using the first i elements” (the answer is dp[n]) and “best answer for something ending exactly at i” (the answer is max(dp) over all i). Contiguous-run problems usually want “ending at i”. Pick one on purpose and write it down.

What it costs

	Time	Space
Plain recursion on a 2-way recurrence	O(2ⁿ) (about O(1.6ⁿ) for Fibonacci)	O(n) stack
DP table, k choices per cell	O(n · k)	O(n)
Rolling variables (reads only the last w cells)	O(n · k)	O(w), often O(1)
Choices depend on all earlier cells (dp[i] = best over j < i)	O(n²)	O(n)

Rule of thumb: time = number of states × work per state. Space = number of states you must keep alive at once.

How fast does work grow?

drag n

O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

n = 16

O(n): 16 opsO(n²): 256 opsO(2ⁿ): 65.5k ops

Variations you’ll meet

• Counting (ways to climb, ways to tile a 2×n board, ways to make change): sums, often modulo 10⁹+7.
• Optimising (min cost, max value): min/max over choices. Keep a parent array to recover the actual choices.
• Feasibility (can you reach the end?): booleans. Often a greedy shortcut exists too.
• Two states per position (e.g. “holding a stock / not holding”, “last element used / not used”): dp[i][0..1]. Still 1-D in spirit; it’s a small state machine. See state machines.
• dp[i] over all j < i: O(n²) shapes where any earlier element may come right before i (chains, partitions into pieces). Some have faster refinements once you spot extra structure.
• Over an amount instead of an index: coin change, where dp[a] reads dp[a − coin]. That’s the bridge to knapsack.

Pitfalls

• Vague state. “dp[i] is the answer at i” is not a definition. Say what is counted or optimised, and over which prefix.
• Wrong base case. dp[0] = 1 (the empty way) vs 0 changes every count. Check n = 0 and n = 1 by hand.
• Off-by-one in indexing. Decide whether dp has n or n + 1 cells. Most prefix DPs need n + 1: dp[i] covers the first i elements.
• Overflow. Counts grow exponentially. Use long in C#, BigInt or a modulus in JS (numbers lose precision past 2⁵³), and apply the modulus at every addition.
• Reading a cell before it’s filled. If the loop order doesn’t match the dependencies, you silently read zeros.
• Returning the wrong cell. For “ending at i” states, the answer is the max over all i, not dp[n−1].

In the interview

• Start with brute force recursion out loud (“try every last move”). Then point at the repeated calls: “these overlap, so I’ll cache by i”.
• Walk the five steps explicitly. Interviewers grade the state definition more than the code.
• Fill a tiny table by hand (n = 4 or 5) before coding. It catches base-case bugs immediately.
• Then optimise space: “each cell reads only the previous two, so I’ll keep two variables.”
• Expect: “return the actual choices, not just the number”, “what if n is 10⁹?” (matrix exponentiation for linear recurrences), “what if step sizes are large?”.

Check yourself

Check yourself

pick one

Climbing stairs with steps of 1 or 2. Someone sets dp[0] = 0, dp[1] = 1 and dp[i] = dp[i−1] + dp[i−2]. What is dp[2], and is it right?

Adp[2] = 1: wrong, there are 2 ways (1+1 and 2)Bdp[2] = 2: rightCdp[2] = 1: right

Check yourself

pick one

dp[i] = min over j in [i−k, i−1] of dp[j] + cost[i]. What is the time complexity for n cells, done naively?

AO(n)BO(n · k)CO(n²) regardless of k

Check yourself

pick one

Your bottom-up DP reads only dp[i−1] and dp[i−2]. What extra space do you need?

AO(n): DP always needs the tableBO(1): two variablesCO(log n)

Practice on your own

Classic exercises (not gym questions):

• Tribonacci: t(n) = t(n−1) + t(n−2) + t(n−3); then do it in O(1) space.
• Number of ways to tile a 2×n board with 1×2 dominoes.
• Minimum number of perfect squares that sum to n.
• Count binary strings of length n with no two consecutive 1s.
• Cheapest travel plan with 1-day, 7-day and 30-day passes for a given list of travel days.

Go deeper

• Introduction to Algorithms (CLRS), ch. 15 “Dynamic Programming” (ch. 14 in the 4th edition): the four-step method and elements of DP.
• Jeff Erickson, Algorithms, ch. 3 “Dynamic Programming” (free online), which builds every DP from a recursive “backtracking” definition.
• cp-algorithms: introduction to dynamic programming.
• MIT 6.006 (Spring 2020), lectures 15-18 on dynamic programming and the “SRTBOT” framework (subproblems, relate, topological order, base, original, time).

Related

MemoizationTop-down DP: recursion plus a cache.

Dynamic programming: 2DTwo indices: strings, grids and pairs of prefixes.

KnapsackDP over capacities and subsets.

Greedy algorithmsWhen one choice is provably enough, and when it isn't.