Climbing Stairs
Given an integer n, representing the number of steps in a staircase, write a function climbStairs that returns the number of distinct ways to climb to the top of the staircase. Each time you can either climb 1 step or 2 steps. You may assume that n is a non-negative integer.
Examples
Input: n = 1 Output: 1 Explanation: There is only 1 way to climb a staircase with 1 step. Input: n = 2 Output: 2 Explanation: There are 2 ways to climb a staircase with 2 steps: 1. Climb 1 step + 1 step 2. Climb 2 steps directly Input: n = 3 Output: 3 Explanation: There are 3 ways to climb a staircase with 3 steps: 1. Climb 1 step + 1 step + 1 step 2. Climb 1 step + 2 steps 3. Climb 2 steps + 1 step Input: n = 4 Output: 5 Explanation: There are 5 ways to climb a staircase with 4 steps: 1. Climb 1 step + 1 step + 1 step + 1 step 2. Climb 1 step + 1 step + 2 steps 3. Climb 1 step + 2 steps + 1 step 4. Climb 2 steps + 1 step + 1 step 5. Climb 2 steps + 2 steps
Can you come up with a solution that has a O(n) time complexity?
Can you come up with a solution that has a O(1) space complexity?
Solution 1: Dynamic Programming Approach
In this solution, we use dynamic programming to compute the number of distinct ways to climb n stairs. The idea is to build up the solution incrementally by solving subproblems. We initialize a list ways where ways[i] represents the number of ways to reach the ith step.
We start by setting the base cases:
ways[0] = 1(1 way to stay at the ground)ways[1] = 1(1 way to reach the first step, which is a single 1-step)
For each subsequent step i, the number of ways to reach that step is the sum of the ways to reach the previous step (ways[i - 1]) and the step before that (ways[i - 2]). This is because you can get to step i either from step i - 1 with a 1-step or from step i - 2 with a 2-step.
def climb_stairs(n: int) -> int:
if n <= 1:
return 1
# Initialize the base cases
ways = [0] * (n + 1)
ways[0] = 1
ways[1] = 1
# Fill the array with the number of ways to reach each step
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]Time Complexity: The time complexity of this solution is O(n), where n is the number of steps. This is because we iterate through the steps from 2 to n, updating the number of ways for each step.
Space Complexity: The space complexity is O(n) due to the additional array ways used to store the number of ways for each step. If space optimization is needed, this can be reduced to O(1) by keeping only the last two computed values.
Solution 2: Combinatorial Approach
Our solution leverages combinatorial mathematics to calculate the number of distinct ways to climb n stairs. The approach is based on counting the number of valid sequences of steps (1-step and 2-steps) that sum up to n.
We use the binomial coefficient to count the number of ways to arrange a certain number of 1-steps and 2-steps. For each possible number of 2-steps (k), we compute the number of ways to choose k positions from n - k steps (the remaining steps will be 1-steps). This is done using the formula for combinations: , where . The total number of ways is the sum of these combinations for all valid values of k.
import math
def climb_stairs(n: int) -> int:
total_ways = 0
max_two_steps = n // 2
for k in range(max_two_steps + 1):
total_ways += math.comb(n - k, k)
return total_waysTime Complexity: The time complexity of this solution is O(n), where n is the number of steps. This is because we compute the combination for each k from 0 to n // 2, and each combination computation is efficient.
Space Complexity: The space complexity is O(1) as we only use a few additional variables for storing intermediate results, regardless of the input size.
function climbStairs(n) { // 4 iterations of Dynamic Programming solutions: // Step 1: Recursive: // if (n <= 2) return n // return climbStairs(n-1) + climbStairs(n-2) // Step 2: Top-down Memoization // const memo = {0:0, 1:1, 2:2} // function f(x) { // if (x in memo) return memo[x] // memo[x] = f(x-1) + f(x-2) // return memo[x] // } // return f(n) // Step 3: Bottom-up Tabulation // const tab = [0,1,2] // for (let i = 3; i < n+1; i++) { // tab[i] = tab[i-1] + tab[i-2] // } // return tab[n] // Step 4: Bottom-up No Memory (current state only) if (n <= 2) return n let prev = 1, cur = 2 for (let i = 3; i < n+1; i++) { [prev,cur] = [cur, cur+prev] } return cur } // debug your code below console.log(climbStairs(5))