algorithmpro
Dynamic programming: climbing stairs
Count the ways up a staircase taking 1 or 2 steps at a time, by building on smaller answers.
- time
- O(n)
- space
- O(n)
// step through it
step 1 / 8
1function climbStairs(n) {2 const dp = new Array(n + 1).fill(0);3 dp[0] = 1;4 dp[1] = 1;5 for (let i = 2; i <= n; i++) {6 dp[i] = dp[i - 1] + dp[i - 2];7 }8 return dp[n];9}- n
- = 6
- 00
- 01
- 02
- 03
- 04
- 05
- 06
Make an array dp, where dp[i] will hold the number of ways to reach step i.
// pro lesson
Unlock the full walkthrough
This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.
See pricingHow it works
To land on step i, your last move came from step i − 1 or step i − 2. So the ways to reach step i are the ways to reach i − 1 plus the ways to reach i − 2. Instead of recomputing those with recursion, store each answer in an array and fill it from the bottom up. Each value is computed once: O(n) time and O(n) space. It is the Fibonacci recursion without the repeated work.
Practice spotting this pattern →