Why it works
- Every climb to step i ends with exactly one last move: a 1-step from i − 1 or a 2-step from i − 2. So the climbs split into two groups with nothing in common, and ways[i] = ways[i − 1] + ways[i − 2].
- ways[0] = 1 is the empty climb before any move. A 2-step from the ground to step 2 extends it, so step 2 gets 1 + 1 = 2 ways, not 1.
- Each cell reads only the two cells before it, which are already filled, so one pass from left to right is enough. Brute force lists every climb one by one, and their number grows exponentially, as fast as the numbers in the cells.
Complexity
Time O(n): each step is filled once with one addition. Memory O(n) for the table; two variables for the last two cells are enough, which gives O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗