Climbing Stairs
Easy
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
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.
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.
Time 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.
Interview experiences
3 sharedRelated courses
