Climbing Stairs
Module 24 · Dynamic Programming
Problem
You're climbing a staircase with n steps. Each move, you can climb
either 1 or 2 steps. Return the number of DISTINCT ways to reach the
top. (LeetCode 70.)
Examples
Example 1
Input
n = 2Output2Explanation. 1+1, or 2
Example 2
Input
n = 3Output3Explanation. 1+1+1, 1+2, 2+1
Constraints
1 ≤ n ≤ 45.
Attempt it first
This is the simplest possible 1D DP, previewed in this module's 1D DP
Patterns concept lesson — it's worth deriving the recurrence yourself
before opening anything. Think about the very LAST move made to reach
step n: what are the only two possibilities for that final move, and
what does each one imply about how many ways exist to have reached the
step just before it?