K AVAILABLE
OPEN TO WORK
← BACK TO KNOWLEDGE

KNOWLEDGE

Climbing Stairs: Dynamic Programming Tabulation

Transform exponential tree recursion into linear O(n) tabulation by identifying overlapping subproblems and optimal substructure.

Updated Sep 4, 20265 min readFoundationalData Structures & Algorithms

INTERACTIVE ALGORITHM WORKBENCH

Climbing Stairs (Dynamic Programming) Visualizer

EasyDynamic ProgrammingTime O(n)Space O(n)
1D Dynamic Programming Table (Tabulation)dp[i] = dp[i-1] + dp[i-2]
Step (i)012target34
Ways dp[i]—12——
Target Step (n)4
Current Step (i)2
Recurrence AddendsBase cases initialized
Subproblem StatusBase values (1, 2) set
solution.py
1def climb_stairs(n: int) -> int:
▶2    if n <= 2:
3        return n
4    dp = [0] * (n + 1)
5    dp[1], dp[2] = 1, 2
6    for i in range(3, n + 1):
7        dp[i] = dp[i - 1] + dp[i - 2]
8    return dp[n]
Step 1 of 6
WHY THIS STEP WORKS

Dynamic programming breaks down a problem into overlapping subproblems with optimal substructure. We initialize known trivial base cases first.

  1. 1Define dp[i] = number of distinct ways to reach step i
  2. 2Base case: dp[1] = 1
  3. 3Base case: dp[2] = 2