70. Climbing Stairs (leetcode, easy)

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

SOLUTION

The problem can be broken down using the Fibonacci sequence because the number of ways to reach step n is the sum of the ways to reach the (n-1)th step and the ways to reach the (n-2)th step:

• To reach step n, you can come from step n-1 (taking 1 step) or from step n-2 (taking 2 steps).
• This relationship mirrors the Fibonacci sequence, where each number is the sum of the two preceding ones.

Example: Climbing 4 Steps

Let's break down the number of ways to climb 4 steps:

Base Cases:

• dp[1] = 1: Only one way to climb 1 step (a single 1-step).
• dp[2] = 2: Two ways to climb 2 steps (1-step + 1-step or 2-steps).

Dynamic Programming Approach:

• We create an array dp of size n + 1 to store the number of ways to reach each step. This ensures we can store values for steps 0 to n.

Filling the DP Array:

• dp[3] = dp[2] + dp[1] → dp[3] = 2 + 1 → dp[3] = 3
• dp[4] = dp[3] + dp[2] → dp[4] = 3 + 2 → dp[4] = 5

def climb_stairs(n)
  return 1 if n == 1
  return 2 if n == 2
  
  dp = Array.new(n + 1, 0)
  dp[1] = 1
  dp[2] = 2
  
  (3..n).each do |i|
    dp[i] = dp[i - 1] + dp[i - 2]
  end
  
  dp[n]
end

# Example
puts climb_stairs(4)  # Output: 5

Explanation

1. Initialization: We handle the base cases for 1 and 2 steps.
2. DP Array: We create an array of size n + 1 initialized to 0.
3. Filling the Array: For each step from 3 to n, we calculate the number of ways to reach that step as the sum of the ways to reach the two preceding steps.

This is a time complexity of O(n) and a space complexity of O(n) too.