70. Climbing Stairs
Problem Description
The problem presents us with a scenario where we are required to climb a staircase that consists of n individual steps. The objective is to determine the total number of distinct ways to reach the top of the staircase.
The constraints that define our approach to climbing are:
- We can take one step at a time (climb
1step). - We can take two steps at a time (climb
2steps).
This means that for each step we take, we have two choices - to take a single step or a double step - unless we are at a point where only one step is needed to reach the top.
To solve this problem, we need to think about it in terms of finding the total combinations of 1-step and 2-step moves that would lead us to the top.
Intuition
To understand the solution's intuition, we can notice that the way to reach a particular step is a combination of the ways to reach the previous two steps (since we can take a step from either of them). This is a classic example of a dynamic programming problem that exhibits the property of overlapping subproblems.
If we look at the smaller subproblems, we can see that:
- To reach the first step, there is exactly 1 way (climb
1step). - To reach the second step, there are 2 ways (climb
1step +1step or climb2steps directly).
For any higher step i, the ways to reach it is the sum of the ways to reach step (i-1) and step (i-2). This is because we can arrive at step i by taking a single step from (i-1) or a double step from (i-2).
We translate this recursive relationship into an iterative solution by using two variables, a and b, to store the number of ways to reach the current and the next step. We then use a simple loop to iterate through the steps, updating a and b at each iteration. At each step in our loop, a takes the value of b (the number of ways to get to the previous step), and b becomes a+b (the number of ways to get to the current step from the two steps before it). By the time we reach the top of the staircase, b will hold the total number of distinct ways to reach the top.
Learn more about Memoization, Math and Dynamic Programming patterns.
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Approach
The implementation of the solution uses a simple iterative algorithm that employs the dynamic programming approach to solve the problem efficiently by avoiding recomputation of the same subproblems.
Here is a step-by-step breakdown of the algorithm, reflecting on the provided Python code:
-
First, we initialize two variables,
aandb, to 0 and 1, respectively. These variables will help us keep track of the number of ways to reach the current step and the next step. In dynamic programming terms,arepresents the solution to the subproblem ati-1andbrepresents the solution to the subproblem ati. -
We then use a
forloop to iterate exactlyntimes, wherenis the total number of steps in the staircase. In each iteration, we perform the following actions:- We update the variable
ato hold the value ofb, which represents the number of ways to reach the current step. - We update the variable
bto hold the sum of the old values ofaandb. The value ofbnow represents the total number of ways to reach the next step as it sums the ways of getting to the two preceding steps (exploiting the fact that steps(i-1)and(i-2)contribute to the number of ways to reach stepi).
- We update the variable
-
This process is repeated until we have iterated through all the steps, effectively building up the number of ways to reach higher steps based on the number of ways to reach the previous two steps.
-
At the end of the loop, the variable
bwill contain the total number of distinct ways we can climb to the top of the staircase.
No additional data structures are needed since we're only keeping track of the solution for the two most recent subproblems at any time, making the space complexity O(1) - constant space. The time complexity of this algorithm is O(n) since we are only looping once through the steps from 1 to n.
The elegance of this solution lies in its simple yet powerful usage of the Fibonacci sequence pattern, where the number of ways to reach a given step is the sum of the number of ways to reach the two preceding steps, just like the Fibonacci numbers are the sum of the two preceding numbers in the sequence.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Example Walkthrough
Let's use an example where n = 4, which represents a staircase with 4 steps to illustrate the solution approach.
For the first step (n = 1), there is 1 distinct way to reach the top: by taking 1 step.
For the second step (n = 2), there are 2 distinct ways:
- Take 1 step twice (1 + 1).
- Take 2 steps once.
For the third step (n = 3), we need to sum the ways to reach n = 1 and n = 2 because we can get to the third step by taking:
- 1 step from the second step (which has 2 ways as calculated before) or
- 2 steps from the first step (which has 1 way as calculated before).
So the total number of ways to reach
n = 3is1 (from n=1) + 2 (from n=2) = 3ways.
Now, let's calculate the distinct ways to reach the top of the staircase with 4 steps (n = 4):
- Initialize two variables:
a = 0(representingn = 0),b = 1(representingn = 1). - We iterate starting with
n = 2ton = 4.- For
n = 2:abecomesb(1), andbbecomesa + b(0 + 1 = 1). Nowa = 1,b = 1. - For
n = 3:abecomesb(1), andbbecomesa + b(1 + 1 = 2). Nowa = 1,b = 2. - For
n = 4:abecomesb(2), andbbecomesa + b(1 + 2 = 3). Nowa = 2,b = 3.
- For
- After completing the loop, the value of
bis 3, which represents the total number of distinct ways to reach the top of a staircase with 4 steps.
Thus, there are 3 distinct ways to climb to the top of a 4-step staircase:
- 1 + 1 + 1 + 1 (taking one step at a time)
- 1 + 2 + 1 (taking a double step after the first step)
- 2 + 1 + 1 (taking a double step from the bottom)
By following the solution approach given in the content, we can deduce that for any given number of steps n, we can use the dynamic programming iterative algorithm to find the total number of distinct ways to climb to the top. This approach efficiently solves the problem by building upon the number of ways to reach the smaller steps and is optimized to use only constant space.
Solution Implementation
1class Solution:
2 def climbStairs(self, n: int) -> int:
3 # Initialize two variables that represent the base cases:
4 # prev_step represents the number of ways to reach the step before the current one
5 # curr_step represents the number of ways to reach the current step. Initially set to 1 because there's 1 way to be at the first step.
6 prev_step, curr_step = 0, 1
7
8 # Loop for each step up to the nth step
9 for _ in range(n):
10 # At each step, the number of ways to reach the current step is the sum of the ways to reach the previous two steps.
11 prev_step, curr_step = curr_step, prev_step + curr_step
12
13 # After finishing the loop, curr_step contains the total number of ways to reach the nth step.
14 return curr_step
151class Solution {
2
3 // This method calculates the number of distinct ways to climb to the top.
4 public int climbStairs(int n) {
5 int first = 0, second = 1;
6
7 // Loop through number of steps n
8 for (int i = 0; i < n; i++) {
9 // Calculate next number in the series
10 int next = first + second;
11
12 // Update the previous two numbers for next iteration
13 first = second;
14 second = next;
15 }
16
17 // The 'second' variable holds the total ways to reach the top
18 return second;
19 }
20}
211class Solution {
2public:
3 // Function to calculate the number of ways to climb n stairs,
4 // where each time you can climb 1 or 2 steps.
5 int climbStairs(int n) {
6 // Initialize variables to store previous two results
7 int prevStep = 0; // Corresponds to the number of ways to climb to the previous step
8 int currentStep = 1; // Corresponds to the number of ways to climb to the current step
9
10 // Loop through the number of stairs to calculate the number of ways
11 for (int i = 0; i < n; ++i) {
12 // Calculate the number of ways to climb to the next step
13 int nextStep = prevStep + currentStep; // Sum of the previous two results
14
15 // Update variables for the next iteration
16 prevStep = currentStep; // The current step becomes the previous step for the next iteration
17 currentStep = nextStep; // The calculated next step becomes the current step for the next iteration
18 }
19
20 // Return the number of ways to climb to the top step
21 return currentStep;
22 }
23};
241// Function to calculate the number of distinct ways to climb to the top of a staircase
2// with n steps, where you can either climb 1 or 2 steps at a time.
3function climbStairs(n: number): number {
4 // Initialize two variables to store the number of ways to climb to the
5 // current step (current) and the previous step (previous).
6 let previous = 1;
7 let current = 1;
8
9 // Loop through the steps from 1 to n - 1.
10 // No loop iteration for the first step as there is only one way to climb one step.
11 for (let i = 1; i < n; i++) {
12 // Update the number of ways for the current step by adding the number
13 // of ways to climb to the previous step to the number of ways for
14 // the step before it (previous + current will give us the new current).
15 [previous, current] = [current, previous + current];
16 }
17
18 // Return the number of ways to climb to the top of the staircase, which will
19 // be stored in 'current' after the loop finishes.
20 return current;
21}
22Which type of traversal does breadth first search do?
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n), where n is the input number of steps. This is because there is a single loop which iterates n times, and within each iteration, a constant-time operation is performed.
Space Complexity
The space complexity of the code is O(1) as only two variables a and b are used irrespective of the input size, which means the amount of space used does not grow with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.