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.
1import java.util.*;
2
3public class Solution {
4 private Map<Integer, Integer> memo = new HashMap<>();
5
6 public int climbStairs(int n) {
7 if (n <= 2) return n;
8 if (memo.containsKey(n)) return memo.get(n);
9 int result = climbStairs(n - 1) + climbStairs(n - 2);
10 memo.put(n, result);
11 return result;
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 System.out.println(sol.climbStairs(3));
17 }
18}This Java solution employs a HashMap to implement memoization. Each time a subproblem is solved, it's stored in the memo HashMap. This avoids redundant computation and enhances the efficiency of the recursive approach.
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 <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int climbStairs(int n) {
8 if (n <= 2) return n;
9 vector<int> dp(n + 1, 0);
10 dp[1] = 1;
11 dp[2] = 2;
12 for (int i = 3; i <= n; ++i) {
13 dp[i] = dp[i - 1] + dp[i - 2];
14 }
15 return dp[n];
16 }
17};
18
19int main() {
20 Solution sol;
21 cout << sol.climbStairs(3);
22 return 0;
23}This C++ solution implements a dynamic programming strategy with a vector to store interim results. The number of ways to reach each step is determined by summing the ways to reach the two preceding steps, efficiently computing results non-recursively.