Problem Statement:
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?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
Constraints
1 <= n <= 45
Approach:
- Identify the recurrence relation:
- To reach
step n, there are only two possibilities:- You came from
step n-1(taking 1 step). - You came from
step n-2(taking 2 steps).
- You came from
- So, the total ways to reach
step nis:
dp[n] = dp[n-1] + dp[n-2] - To reach
- Base cases:
dp[1] = 1→ Only 1 way to climb 1 step.dp[2] = 2→ Either take two 1-steps or one 2-step.
- DP array construction:
- We create an array dp where
dp[i]represents the number of ways to reach step i. - Start from
i = 3and use therecurrence relation to fill the array.
- We create an array dp where
Return dp[n], which contains the number of ways to reach thenth step.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(n)
Dry Run
Input: n = 5
Step 0: Start Function: climbStairs(5) n = 5 dp = [0, 1, 2] // base cases Iteration (i = 3): - dp[3] = dp[2] + dp[1] = 2 + 1 = 3 - dp = [0, 1, 2, 3] Iteration (i = 4): - dp[4] = dp[3] + dp[2] = 3 + 2 = 5 - dp = [0, 1, 2, 3, 5] Iteration (i = 5): - dp[5] = dp[4] + dp[3] = 5 + 3 = 8 - dp = [0, 1, 2, 3, 5, 8] Loop ends (i > n) Step 3: End Return dp[5] = 8
Output: 8
Visualisation:
var climbStairs = function(n) {
let dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
def climbStairs(n):
dp = [0, 1, 2]
for i in range(3, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
#include <vector>
using namespace std;
int climbStairs(int n) {
vector dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
#include <stdio.h>
#include <stdlib.h>
int climbStairs(int n) {
int* dp = (int*)malloc((n + 1) * sizeof(int));
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int result = dp[n];
free(dp);
return result;
}
public class Solution {
public int ClimbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
