dynamic-programming · Problem 1 of 5
Climbing Stairs
easy
Amazon
Adobe
AmazonAdobeYou climb 1 or 2 steps at a time. Return how many distinct ways there are to reach step n.
climbStairs(3) -> 3Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| climbStairs(1) | one step | 1 | — |
| climbStairs(2) | two steps | 2 | — |
| climbStairs(3) | three steps | 3 | — |
| climbStairs(10) | ten steps | 89 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1)
The naive recursion is O(2^n). Keeping two variables instead of a table drops the space from O(n) to constant.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left