Dynamic Programming
LC #70Easy
Climbing Stairs
Dynamic Programming
AmazonGoogleBloombergMicrosoftProblem
Count the number of ways to climb n stairs, taking 1 or 2 steps at a time.
dynamic-programmingmathmemoization
Constraints
- ›1 ≤ n ≤ 45
Example
Input
n = 5Output
8Why
Ways: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1 = 8