🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to determine the number of distinct ways to climb a staircase with n
steps, where you can either take 1 step or 2 steps at a time.
Intuition
The number of ways to reach a particular step is the sum of the ways to reach the previous step and the step before that. This is because to reach a step i
, you can come from step i-1
with a single step or from step i-2
with a two-step jump. This forms the basis of a dynamic programming solution.
Approach
- Base Cases:
- If
n
is0
or1
, there's only one way to climb the stairs, which is doing nothing or taking a single step. - Dynamic Programming Array:
- Create an array
dp
wheredp[i]
represents the number of ways to reach stepi
. - Initializedp[0]
anddp[1]
to1
. - Iterate and Fill:
- For each step from
2
ton
, setdp[i]
to the sum ofdp[i-1]
anddp[i-2]
because you can either come from the previous step or the step before that. - Result:
- The value at
dp[n]
will be the number of ways to reach then
th step.
Complexity
Time Complexity:
O(n), since we are iterating from 2
to n
to fill the dp
array.
Space Complexity:
O(n), due to the dp
array that stores the number of ways to reach each step up to n
.
Code
C++
class Solution {
public:
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
vector dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
Python
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Java
class Solution {
public int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
JavaScript
var climbStairs = function (n) {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};