70. Climbing Stairs - Detailed Explanation

Problem Statement

Description:
You are climbing a staircase that has n steps. Each time you can either climb 1 or 2 steps. Your task is to determine in how many distinct ways you can climb to the top.

Key Details:

• You can take either 1 or 2 steps at a time.
• The order in which you take the steps matters.
• The problem asks for the total number of distinct ways to reach the top.

Example Inputs, Outputs, and Explanations

1. Example 1:

   • Input: n = 2
   • Output: 2
   • Explanation:
     • There are two ways to climb 2 steps:
       1. 1 step + 1 step.
       2. A single 2-step jump.

2. Example 2:

   • Input: n = 3
   • Output: 3
   • Explanation:
     • There are three ways to climb 3 steps:
       1. 1 step + 1 step + 1 step.
       2. 1 step + 2 steps.
       3. 2 steps + 1 step.

3. Example 3 (Edge Case):

   • Input: n = 1
   • Output: 1
   • Explanation:
     • Only one step is available, so there is only one way to climb it.

Constraints

• n is a positive integer (typically, 1 ≤ n ≤ 45).
• The solution should be efficient to handle the upper bound of n.

Hints to Approach the Solution

1. Think Recursively:

   • To reach step n, you can come from either step n - 1 (by taking 1 step) or step n - 2 (by taking 2 steps). This observation naturally leads to a recurrence relation.

2. Dynamic Programming:

   • Since the recurrence relation for climbing stairs has overlapping subproblems, you can use dynamic programming (either top-down with memoization or bottom-up) to efficiently solve the problem.

3. Fibonacci Connection:

   • Notice that the number of ways to climb to step n follows a Fibonacci-like sequence. Specifically, if we denote dp[i] as the number of ways to reach step i, then: [ dp[i] = dp[i - 1] + dp[i - 2] ]
   • With base cases: dp[0] = 1 (one way to stand at the bottom) and dp[1] = 1 (one way to climb the first step).

Approach 1: Recursive with Memoization

Explanation

• Method:
  • Define a recursive function that computes the number of ways to reach the nth step.
  • Use memoization to cache the results of subproblems and avoid repeated calculations.
• Pros:
  • Easy to understand and implement.
• Cons:
  • Recursive calls might add overhead, and a bottom-up approach can be more space/time efficient.

Pseudocode

function climb(n):
    if n <= 1: return 1
    if memo[n] exists: return memo[n]
    memo[n] = climb(n - 1) + climb(n - 2)
    return memo[n]

Approach 2: Bottom-Up Dynamic Programming

Explanation

• Method:
  • Create an array dp where dp[i] represents the number of ways to reach step i.
  • Fill in the array iteratively using the recurrence relation.
• Pros:
  • Iterative solution, which is straightforward and efficient.
• Cons:
  • Uses O(n) extra space. However, this can be optimized further.

Pseudocode

dp[0] = 1, dp[1] = 1
for i from 2 to n:
    dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]

Approach 3: Fibonacci Number Optimization (Constant Space)

Explanation

• Method:
  • Realize that only the last two values are needed at any step.
  • Maintain two variables and update them iteratively.
• Pros:
  • Uses O(1) space and is very efficient.
• Cons:
  • Slightly less intuitive if you are not familiar with Fibonacci sequences.

Pseudocode

a = 1, b = 1
for i from 2 to n:
    temp = a + b
    a = b
    b = temp
return b

Code Implementations

Python Code