Easy · One-Dimensional DP
Understand → Visualise → Practice.
The final move to stair n came from n − 1 or n − 2, so the number of routes is the sum of those smaller answers.
ways[n] = ways[n − 1] + ways[n − 2], with ways[0] = ways[1] = 1.
ways[i] counts routes to stair i.
There is one way to stand at 0 or reach 1.
Keep only the previous two counts.
O(n) time and O(1) space.
ways[0] is 1, representing the one empty sequence of steps.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.