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 <stdio.h>
2#define MAX 46
3
4int memo[MAX] = {0};
5
6int climbStairs(int n) {
7 if (n == 1) return 1;
8 if (n == 2) return 2;
9 if (memo[n] != 0) return memo[n];
10 memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
11 return memo[n];
12}
13
14int main() {
15 int n = 3;
16 printf("%d", climbStairs(n));
17 return 0;
18}This C code provides a recursive solution enhanced with memoization. We define an array memo to store the results of previously solved subproblems. This helps in reducing redundant calculations, thus optimizing the recursive solution.
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.
1public class Solution {
2 public int climbStairs(int n) {
3 if (n <= 2) return n;
4 int[] dp = new int[n + 1];
5 dp[1] = 1;
6 dp[2] = 2;
7 for (int i = 3; i <= n; i++) {
8 dp[i] = dp[i - 1] + dp[i - 2];
9 }
10 return dp[n];
11 }
12 public static void main(String[] args) {
13 Solution sol = new Solution();
14 System.out.println(sol.climbStairs(3));
15 }
16}This Java solution uses an array to perform a dynamic programming approach iteratively. Building upon basic cases, this method efficiently calculates the answer using an dp array to store results, avoiding recursive complexity.