03.03 · Problem
Climbing Stairs
You climb a staircase of n steps, 1 or 2 steps at a time. In how many different ways can you reach the top?
Examples
Example 1
Input: n = 2
Output: 21 + 1, or 2.
Example 2
Input: n = 3
Output: 31 + 1 + 1, 1 + 2, 2 + 1.
Example 3
Input: n = 1
Output: 1Constraints
1 ≤ n ≤ 45 (the answer fits in an int)
Derive it
Hint
Your first move is 1 step or 2 steps. How many ways are there to finish after each one?
Still stuck? Derive it step by step. Each answer adds a line to the code:
Solution steps
- Promise:
ways(n)= number of ways to climb exactly n steps. - Base cases:
n == 0→ 1 (you’re at the top).n < 0→ 0. - Recurrence:
ways(n − 1) + ways(n − 2). - Memo:
int[n + 1]filled with -1. Time O(n).
Table: dp[0] = dp[1] = 1, then dp[i] = dp[i − 1] + dp[i − 2] going up.
Change one rule: steps of 1, 2 or 3? Add ways(n − 3).
Loading the workspace…
Item 22 of 44 · updated 2026-10-13