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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private Dictionary<int, int> memo = new Dictionary<int, int>();
6
7 public int ClimbStairs(int n) {
8 if (n <= 2) return n;
9 if (memo.ContainsKey(n)) return memo[n];
10 memo[n] = ClimbStairs(n - 1) + ClimbStairs(n - 2);
11 return memo[n];
12 }
13
14 public static void Main(string[] args) {
15 Solution sol = new Solution();
16 Console.WriteLine(sol.ClimbStairs(3));
17 }
18}This C# solution uses a dictionary for memoization. The approach involves recursively calculating the number of ways to go up n stairs and storing interim results in a dictionary to optimize performance.
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.
1class Solution:
2 def climbStairs(self, n: int) -> int:
3 if n <= 2:
4 return n
5 dp = [0] * (n + 1)
6 dp[1], dp[2] = 1, 2
7 for i in range(3, n + 1):
8 dp[i] = dp[i - 1] + dp[i - 2]
9 return dp[n]
10
11solution = Solution()
12print(solution.climbStairs(3))This Python code employs an iterative dynamic programming approach to calculate the number of distinct ways to climb stairs. The dp list stores solutions to subproblems, systematically building up the solution for n steps.