Climbing Stairs (opens in a new tab) Easy

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Summary

To solve this problem, we can use dynamic programming to store the number of ways to reach each step. The number of ways to reach the ith step is the sum of the ways to reach the (i-1)th step and the (i-2)th step.

Solution

In TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;
    let dp = [0, 1, 2];
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

In Python

def climbStairs(self, n: int) -> int:
		if n <= 2:
				return n
		dp = [0, 1, 2]
		for i in range(3, n + 1):
				dp.append(dp[i - 1] + dp[i - 2])
		return dp[n]

Step-by-step explanation

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), as we iterate through the dynamic programming array once.

Space Complexity

The space complexity of this solution is O(n), as we store the number of ways to reach each step in an array.