DPAlgorithmaka bottom-up DP, iterative DP, table filling

Tabulation (Bottom-Up DP)

Fill a table of subproblem answers in an explicit order from base cases upward, with loops instead of recursion.

▶ Visualize Pattern: Dynamic Programming Practice (6)

Progress

Overview

Tabulation evaluates the same DAG of subproblems as Memoization (Top-Down DP), but explicitly: allocate a table, write the base cases, then loop through states in an order where every dependency is already filled. There is no recursion, so there is no stack limit and no call overhead.

Because you control the order, you can also control the memory. If row i depends only on row i-1, keep two rows. If dp[i] depends only on dp[i-1] and dp[i-2], keep two variables — that is how Fibonacci Numbers and Climbing Stairs run in O(1) space, and how 0/1 Knapsack drops from O(nW) to O(W).

The cost is that you must find the dependency order yourself (which is the point of step 4 in the Dynamic Programming framework), and you evaluate every state, reachable or not. For most interview problems the whole table is reachable anyway and tabulation is the preferred final form.

bottom-upiterativetablespace optimizationtopological order

Intuition

A mental model before the formal terms.

Memoization is a lazy student starting from the last question and looking things up as needed. Tabulation is a methodical one starting from question 1 and answering every question in order, knowing each answer only needs earlier ones. Same notebook, opposite direction, no backtracking.

Climbing stairs: the number of ways to reach step i is ways[i-1] + ways[i-2]. Standing at the bottom you know ways[0] = 1, ways[1] = 1; walk up one step at a time and each new count is the sum of the two below you. You only ever need to remember the last two.

How it works

Define the state and the recurrence exactly as for top-down DP.
Identify which states each state depends on, and choose a loop order in which those are always already computed: increasing index for prefix DPs, increasing length for interval DPs, increasing mask value (which implies increasing popcount when transitions only add bits), children-before-parents for trees.
Allocate the table with one extra slot for the base case (dp[0] = "nothing processed"), fill base cases, then run the loops writing each state from its dependencies.
Read the answer from the final cell or aggregate over cells.
Reduce space: replace the table by the minimal window of previous rows/values the transition touches. Check the direction of the inner loop when a single row is reused (see Knapsack DP).

Why it works

The loops enumerate a topological order of the state DAG, so when dp[s] is computed, every dp[t] it reads holds its final, correct value. Induction over that order gives correctness.

Every state is written exactly once and read a bounded number of times, so time is (states) × (transition cost) with a small constant: array indexing and arithmetic only.

Recognition

How to tell a problem wants this.

The recurrence indices decrease in a regular way (i-1, i-2, j-1), so a simple loop order exists.
The state count is large (10^6–10^8) and recursion would overflow or be too slow.
The problem asks for space optimization or the interviewer asks "can you do it without recursion?".

“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Climbing Stairs visualization.

Steps n — Integer between 2 and 15

0	1	2	3	4	5	6	7	8
1	1	·	·	·	·	·	·	·

1/16Base cases: there is 1 way to stand on step 0 (do nothing) and 1 way to reach step 1 (a single step).

Cell being filledDependency readBase caseComputedReconstructed choice

PseudocodeLearn Climbing Stairs →

1dp[0] = 1; dp[1] = 1
2for i in 2 .. n:
3  dp[i] = dp[i-1] + dp[i-2]
4return dp[n]

Variables

Complexity

best O(n)

avg O(n)

worst O(n)

space O(1)

Speed

Pseudocode

1# climbing-stairs: ways[i] = ways[i-1] + ways[i-2]
2if n <= 1: return 1
3prev2 = 1  # ways[0]
4prev1 = 1  # ways[1]
5for i in 2..n:
6  cur = prev1 + prev2
7  prev2 = prev1
8  prev1 = cur
9return prev1

Implementations

1# Representative problem: climbing stairs (1 or 2 steps at a time), bottom-up
2def climb_stairs(n: int) -> int:
31 · Allocate the table
4    dp = [0] * (n + 2)              # n + 2 so dp[1] exists even when n == 0
52 · Base cases
6    dp[0] = 1                       # one way to stand at the bottom
7    dp[1] = 1
83 · Fill in dependency order
9    for i in range(2, n + 1):       # i-1 and i-2 are already written
10        dp[i] = dp[i - 1] + dp[i - 2]
114 · Read the answer
12    return dp[n]
13 
14 
155 · Space-optimized rolling variables
16def climb_stairs_o1(n: int) -> int:
17    prev2, prev1 = 1, 1             # ways[i-2], ways[i-1]
18    for _ in range(2, n + 1):
19        prev2, prev1 = prev1, prev1 + prev2
20    return prev1
21 
22 
23if __name__ == "__main__":
24    print(climb_stairs(10), climb_stairs_o1(10))  # 89 89

Walkthrough

[0] * (n + 2) is a safe way to build a 1D table — ints are immutable so there is no aliasing.
Base cases dp[0] = dp[1] = 1, then range(2, n + 1) fills each cell from the two below it.
climb_stairs_o1 uses tuple assignment prev2, prev1 = prev1, prev1 + prev2: the right-hand side is evaluated fully before either name is rebound, so no temp is needed.
Python ints are unbounded, so climb_stairs(1000) is exact without any special type.
Both functions print 89 for n = 10.

Complexity (this implementation)

time O(n) · space O(n) table, O(1) with rolling variables

Language notes

Tuple assignment is the idiomatic rolling-variable swap; it reads clearly and avoids ordering bugs.
A tight loop over range is 30–100× faster than the equivalent memoized recursion in CPython.
For 2D tables build rows with a comprehension ([[0] * m for _ in range(n)]), never [[0] * m] * n.

Common mistakes in this language

[[0] * m] * n — every row is the same list object; writing one cell changes every row.
dp = [0] * n (not n + 2) and then dp[n] → IndexError.
Writing the O(1) version as two separate statements in the wrong order.

Language differences that matter here

Overflow: C++ long long overflows at n = 93, JS/TS numbers lose exactness at n = 78, Python is exact for any n.
Row copying in 2D tabulation: Python [[0]*m]*n and JS new Array(n).fill([]) both alias one inner list/array; C++ std::vector<std::vector<>> copies by value.
Rolling variables: Python tuple assignment swaps atomically; C++/JS/TS need a temporary or (JS/TS) array destructuring.

Complexity

Best

—

Average

—

Worst

O(states × transition cost)

Space

O(states), reducible to O(window of dependencies)

No recursion stack. Evaluates all states, including unreachable ones.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Final, production-quality DP: fastest constant factor and no stack risk.
Space matters — rolling arrays only work bottom-up.
The state space is dense (most states are reachable) and the loop order is obvious.

Avoid it when

The reachable state set is tiny compared to the full table — memoization avoids the wasted work.
The dependency order is irregular and hard to loop over correctly (deep interval or digit DPs are often cleaner top-down).
While still discovering the recurrence — write it recursively first, then convert.

Alternatives

Memoization (Top-Down DP)Dynamic Programming

Compare: Memoization vs Tabulation

Common mistakes

Iterating in an order that reads cells not yet computed (e.g. filling a 2D table column-major when the recurrence reads dp[i][j-1] from the same row).
When rolling to a single row in 0/1 knapsack, iterating capacity upward so each item is counted multiple times (that is Unbounded Knapsack).
Off-by-one sizing: the table needs n + 1 slots to hold the "zero items / empty prefix" base case.
Copying rows with dp[i] = dp[i-1] in languages where that aliases the same array (JavaScript, Python).

Interview patterns

Convert a memoized solution to bottom-up, then reduce to O(1) or O(m) space — a common two-step follow-up.
Explain the loop order as a topological order of the subproblem DAG.
Reconstruct the chosen path by keeping a parent/choice array alongside the value table.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Recursion versus iterationIntermediate
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Climbing Stairseasy House Robbermedium Coin Changemedium Longest Common Subsequencemedium Partition Equal Subset Summedium Unique Pathsmedium

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related