This approach uses recursion to explore the different ways to reach the top. To optimize, we use memoization to store results of subproblems to avoid redundant calculations. This ensures that each subproblem is solved only once, dramatically improving efficiency.
Time Complexity: O(n), as each state is only computed once.
Space Complexity: O(n), due to the memoization array.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> memo;
8 int climbStairs(int n) {
9 memo.resize(n + 1, 0);
10 return climb(n);
11 }
12private:
13 int climb(int n) {
14 if(n <= 2) return n;
15 if(memo[n] != 0) return memo[n];
16 memo[n] = climb(n - 1) + climb(n - 2);
17 return memo[n];
18 }
19};
20
21int main() {
22 Solution sol;
23 cout << sol.climbStairs(3);
24 return 0;
25}This C++ solution uses a class to manage memoization. The climbStairs function initializes a memoization vector and then uses a helper function climb to recursively calculate the number of ways to climb n stairs.
This approach builds from the base up using a table to store results at each step. Starting with known base cases, each subsequent result is built by combining previous results. This eliminates the recursive overhead, making it a very efficient algorithm.
Time Complexity: O(n), since each value is calculated sequentially in a loop.
Space Complexity: O(n), for storing the results in the dp array.
1#include <stdio.h>
2
3int climbStairs(int n) {
4 if (n <= 2) return n;
5 int dp[n+1];
6 dp[1] = 1;
7 dp[2] = 2;
8 for (int i = 3; i <= n; ++i) {
9 dp[i] = dp[i-1] + dp[i-2];
10 }
11 return dp[n];
12}
13
14int main() {
15 int n = 3;
16 printf("%d", climbStairs(n));
17 return 0;
18}This C code uses dynamic programming to solve the problem iteratively with a dp array. It starts with known results for 1 step and 2 steps and iteratively computes the number of ways for all steps up to n, reducing the time complexity compared to a naive recursive approach.