Leetcode: 70. Climbing Stairs

Climbing Stairs - A Dynamic Programming Solution

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

class Solution {
public:
  int climbStairs(int n) {
    return climb_Stairs(0, n);
  }

  int climb_Stairs(int i, int n) {
    if (i > n)
      return 0;
    else if (i == n)
      return 1;
    return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n); 
  }
};
  

Complexity Analysis

The given solution uses a recursive approach to solve the problem. Let's analyze its time complexity:

• The function climbStairs is called once, which has a time complexity of O(1).
• The recursive function climb_Stairs is called twice in each recursive call. It can branch into two recursive calls, each reducing the problem size by 1 or 2 steps.
• The maximum depth of the recursive tree is n, and at each level, we have two recursive calls.
• Therefore, the total number of nodes (function calls) in the recursive tree is O(2ⁿ).

Hence, the overall time complexity of this solution is O(2ⁿ).

Example

Let's consider an example to understand how the solution works:

#include <iostream>
using namespace std;

int main() {
  Solution s;
  int n = 4;
  int distinctWays = s.climbStairs(n);
  cout << "Number of distinct ways to climb " << n << " stairs: " << distinctWays << endl;
  return 0;
}
  

Output:

Number of distinct ways to climb 4 stairs: 5
  

Conclusion

The given code provides a solution to find the number of distinct ways to climb a staircase with n steps, where each time you can either climb 1 or 2 steps. However, the current implementation has exponential time complexity, which may not be efficient for large inputs.

Consider using dynamic programming or memoization techniques to optimize the solution and reduce the time complexity to O(n). These approaches can be explored further to improve the efficiency of the solution.