Pattern visualizer
Climbing Stairs
Every path that reaches step i has to end with one specific last move — a single step up from i-1, or a double step up from i-2 — and those two cases cover every possibility with no overlap, so the count for step i is simply the count for i-1 plus the count for i-2. Instead of recursing top-down and re-solving the same stairs over and over, fill a table bottom-up so dp[i-1] and dp[i-2] are already final by the time dp[i] needs them. Animated on: Climbing Stairs: you can climb 1 or 2 steps at a time — how many distinct ways to reach the top of n = 6 stairs?.
Bottom-up table fill — the canonical first DP
n = 6 stairs. Build a table dp[0..6] where dp[i] = number of distinct ways to reach step i. Bottom-up DP: solve the tiny cases first, then combine them upward.
1FUNCTION climbStairs(n):2 dp = a table of size n + 13 dp[0] = 1, dp[1] = 14 FOR i from 2 to n:5 dp[i] = dp[i-1] + dp[i-2]6 RETURN dp[n]
← / → step · space play · Home restart