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.
1function climbStairs(n) {
2 const memo = {};
3 function climb(n) {
4 if (n <= 2) return n;
5 if (n in memo) return memo[n];
6 return memo[n] = climb(n - 1) + climb(n - 2);
7 }
8 return climb(n);
9}
10
11console.log(climbStairs(3));This JavaScript solution leverages a helper function to recursively calculate stairs traversed, optimizing through memoization. The memo object stores previous results to avoid extra calculations.
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.
1function climbStairs(n) {
2 if (n <= 2) return n;
3 const dp = new Array(n + 1).fill(0);
4 dp[1] = 1;
5 dp[2] = 2;
6 for (let i = 3; i <= n; i++) {
7 dp[i] = dp[i - 1] + dp[i - 2];
8 }
9 return dp[n];
10}
11
12console.log(climbStairs(3));This JavaScript code implements a dynamic programming solution with an array dp tracking the number of ways to climb stairs. Using a simple iteration through the range, it calculates each step's solutions sequentially.