Dare2Solve
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.
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.
n
is 0
or 1
, there's only one way to climb the stairs, which is doing nothing or taking a single step.dp
where dp[i]
represents the number of ways to reach step i
.dp[0]
and dp[1]
to 1
.2
to n
, set dp[i]
to the sum of dp[i-1]
and dp[i-2]
because you can either come from the previous step or the step before that.dp[n]
will be the number of ways to reach the n
th step.O(n), since we are iterating from 2
to n
to fill the dp
array.
O(n), due to the dp
array that stores the number of ways to reach each step up to n
.
class Solution {
public:
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
vector<int> 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];
}
};
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]
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];
}
}
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];
};