Description:
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?
Examples:
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 stepSolution in Python:
Python
class Solution:
def climbStairs(self, n: int) -> int:
# Base cases for when there are 1 or 2 steps
if n == 1:
return 1
if n == 2:
return 2
# Initialize the base values for the first two steps
prev1, prev2 = 2, 1
# Iterate from the 3rd step to the nth step
for i in range(3, n + 1):
current = prev1 + prev2 # The current number of ways is the sum of the previous two
prev2 = prev1 # Update prev2 to the previous value of prev1
prev1 = current # Update prev1 to the current value
return prev1 # Return the number of ways to reach the nth stepExplanation:
- Base Cases:
- If
nis 1, there is only one way to climb the stairs: one step. - If
nis 2, there are two ways to climb the stairs: either two single steps (1+1) or one double step (2).
- If
- Dynamic Programming Initialization:
- Initialize
prev1to 2 (number of ways to climb 2 steps). - Initialize
prev2to 1 (number of ways to climb 1 step).
- Initialize
- Iterative Calculation:
- For each step from 3 to
n, calculate the number of ways to reach that step as the sum of the ways to reach the previous step (prev1) and the step before that (prev2). - Update
prev2to the previous value ofprev1. - Update
prev1to the current calculated value.
- For each step from 3 to
- Return Result:
- After iterating through all the steps,
prev1will hold the number of distinct ways to reach thenth step.
- After iterating through all the steps,
This approach ensures that the problem is solved efficiently with a time complexity of O(n) and a space complexity of O(1).
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
// Base cases for when there are 1 or 2 steps
if (n === 1) {
return 1;
}
if (n === 2) {
return 2;
}
// Initialize the base values for the first two steps
let prev1 = 2;
let prev2 = 1;
// Iterate from the 3rd step to the nth step
for (let i = 3; i <= n; i++) {
let current = prev1 + prev2; // The current number of ways is the sum of the previous two
prev2 = prev1; // Update prev2 to the previous value of prev1
prev1 = current; // Update prev1 to the current value
}
return prev1; // Return the number of ways to reach the nth step
};Solution in Java:
Java
class Solution {
public int climbStairs(int n) {
// Base cases for when there are 1 or 2 steps
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// Initialize the base values for the first two steps
int prev1 = 2;
int prev2 = 1;
// Iterate from the 3rd step to the nth step
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2; // The current number of ways is the sum of the previous two
prev2 = prev1; // Update prev2 to the previous value of prev1
prev1 = current; // Update prev1 to the current value
}
return prev1; // Return the number of ways to reach the nth step
}
}Solution in C#:
C#
public class Solution {
public int ClimbStairs(int n) {
// Base cases for when there are 1 or 2 steps
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// Initialize the base values for the first two steps
int prev1 = 2;
int prev2 = 1;
// Iterate from the 3rd step to the nth step
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2; // The current number of ways is the sum of the previous two
prev2 = prev1; // Update prev2 to the previous value of prev1
prev1 = current; // Update prev1 to the current value
}
return prev1; // Return the number of ways to reach the nth step
}
}