Climbing Stairs easy

Problem Statement

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 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

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

Steps to Solve

This problem can be solved using dynamic programming. Let dp[i] represent the number of distinct ways to climb to the i-th step.

1. Base Cases:

   • dp[0] = 1 (There's one way to reach step 0: do nothing)
   • dp[1] = 1 (There's one way to reach step 1: take one step)

2. Recursive Relation: To reach step i, you can either come from step i-1 (by taking a single step) or from step i-2 (by taking two steps). Therefore: dp[i] = dp[i-1] + dp[i-2]

3. Iteration: Iterate from i = 2 to n, calculating dp[i] using the recursive relation.

4. Result: dp[n] will contain the total number of distinct ways to climb to the top.

Explanation

The dynamic programming approach avoids redundant calculations. Instead of recursively exploring all possible paths (which would be highly inefficient), it builds up a solution bottom-up. Each dp[i] is calculated only once and reused in subsequent calculations. This makes the algorithm significantly faster than a purely recursive approach.

Code (Python)

def climbStairs(n: int) -> int:
    """
    Calculates the number of distinct ways to climb n stairs, taking 1 or 2 steps at a time.

    Args:
        n: The number of stairs.

    Returns:
        The number of distinct ways to climb the stairs.
    """
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Complexity Analysis

• Time Complexity: O(n). The loop iterates n times.
• Space Complexity: O(n). We use a DP array of size n+1. This could be optimized to O(1) by only storing the last two values of the DP array. However the provided solution is more readable.

def climbStairsOptimized(n: int) -> int:
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

The climbStairsOptimized function achieves O(1) space complexity.