Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top, and each time you can climb either 1 or 2 steps. Return the number of distinct ways to reach the top. This is a standard choice-DP problem with a simple recurrence.

Input Format

n = number of stairs

Output Format

number of distinct ways to reach the top

Constraints

  • 1 <= n <= 45

Examples

Example 1:

Input:

n = 2

Output:

2

Explanation:

The two ways are (1+1) and (2).

Example 2:

Input:

n = 5

Output:

8

Explanation:

This follows the Fibonacci-style recurrence.

Loading...
Climbing Stairs - Dp Knapsack DSA Problem