Skip to content
BASA DSA

Climbing Stairs

Easy1-D Dynamic Programming

You may climb either one or two steps at a time. Return the number of distinct step sequences that reach exactly n steps.

Example 1

Input
n = 5
Output
8

Explanation

For five steps, counts with zero, one or two two-step moves are 1,4,3, totaling 8.

Example 2

Input
n = 10
Output
89

Explanation

ways(n)=ways(n-1)+ways(n-2) gives 89 for ten steps; move order matters.

Example 3

Input
n = 1
Output
1

Explanation

One step can only be reached with a single one-step move.

Constraints

  • 1 <= n <= 45

Function contractclimbStairsArguments: json
Loading draft…
SolutionRuns on your device