Climbing Stairs
Easy· 1D DP· fibonacci
Problem
You are at the bottom of a staircase with n steps and can move up either 1 or 2 steps at a time. Count how many distinct sequences of moves take you exactly to the top.
Examples
Input: n = 2
Output: 2
Either 1+1 or a single 2-step.
Input: n = 5
Output: 8
Constraints
- • 1 <= n <= 45
Hints & approach
Hint 1
Think about the very last move you make to reach step n.
Hint 2
The last move is either a 1-step from n-1 or a 2-step from n-2.
Hint 3
ways(n) = ways(n-1) + ways(n-2) — you only need the previous two values.
Approachtry the hints first
Let ways[i] be the number of ways to stand on step i. Every path to step i ends with a 1-step from i-1 or a 2-step from i-2, so ways[i] = ways[i-1] + ways[i-2]. The base cases are ways[0] = 1 and ways[1] = 1. Since each value depends only on the previous two, keep two rolling variables instead of an array.
Time O(n) · Space O(1)