Dynamic Programming Recursion Memoization Tabulation
Learner Level

Implement the climbStairsWays method that returns the number of distinct ways to climb n stairs.

The input contains an integer n, representing the number of stairs. You can climb either 1 stair or 2 stairs at a time.

Your task is to return how many distinct ways you can reach the top. For example, when n = 3, the possible ways are 1+1+1, 1+2, and 2+1, so the answer is 3.

Example 1
Input:
n (int) = 2
Return:
(int) 2
Example 2
Input:
n (int) = 3
Return:
(int) 3
Example 3
Input:
n (int) = 5
Return:
(int) 8

To reach stair n, the last move must come from stair n - 1 using one step, or from stair n - 2 using two steps.

So the number of ways to reach stair n is the sum of ways to reach n - 1 and n - 2. This is similar to the Fibonacci sequence.

Pseudocode:

function climbStairsWays(n):
    if n <= 1:
        return 1
    prev2 = 1
    prev1 = 1
    for stair from 2 to n:
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1
Run your code to see the result.