Climbing Stairs
Link: https://leetcode.com/problems/climbing-stairs/
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?
Recursive solution - Gives TLE
class Solution {
public:
int solve(int curr, int n){
if (curr == n) return 1;
if (curr > n) return 0;
return solve(curr+1, n) + solve(curr+2, n);
}
int climbStairs(int n) {
return solve(0, n);
}
};
Memoization solution - Accepted
class Solution {
public:
int solve(int curr, int n, unordered_map<int, int> &dp){
if (curr == n) return 1;
if (curr > n) return 0;
if (dp.find(curr) != dp.end()) return dp[curr];
dp[curr] = solve(curr+1, n, dp) + solve(curr+2, n, dp);
return dp[curr];
}
int climbStairs(int n) {
unordered_map<int, int> dp;
return solve(0, n, dp);
}
};
Tabulationsolution - Accepted
class Solution {
public:
int climbStairs(int n) {
if (n ==0 || n == 1) return 1;
vector<int> dp(n+1);
dp[0] = dp[1] = 1;
for (int i=2; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};