Leetcode: 70. Climbing Stairs (Memoization)

Climbing Stairs - An Optimized 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?

Previous Approach

class Solution {
public:
  int climbStairs(int n) {
    int *memo = new int[n + 1];
    memset(memo, 0, sizeof(int) * (n + 1));
    return climb_Stairs(0, n, memo);
  }

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

Solution

class Solution {
public:
  int climbStairs(int n) {
    if (n == 0 || n == 1)
      return 1;

    int *memo = new int[n + 1];
    memset(memo, 0, sizeof(int) * (n + 1));
    memo[0] = 1;
    memo[1] = 1;

    for (int i = 2; i <= n; i++) {
      memo[i] = memo[i - 1] + memo[i - 2];
    }

    int distinctWays = memo[n];
    delete[] memo;
    return distinctWays;
  }
};
  

Explanation

The previous solution used memoization to avoid redundant calculations and optimize the recursive approach. However, we can further improve the solution using an iterative approach known as dynamic programming.

In the optimized solution, we create an array memo of size n+1 to store the number of distinct ways to climb each step. We initialize the base cases: memo[0] = 1 and memo[1] = 1.

Then, starting from step 2, we iterate through the remaining steps up to n. At each step i, the number of distinct ways to reach that step is the sum of the distinct ways to reach the previous two steps, i.e., memo[i] = memo[i-1] + memo[i-2].

Finally, we return the value of memo[n], which represents the total number of distinct ways to climb to the top of the staircase.

Complexity Analysis

The optimized solution using dynamic programming has the following time and space complexity:

• The time complexity is O(n) because we iterate through all the steps once to calculate the distinct ways using the previous two steps.
• The space complexity is O(n) because we use an array of size n+1 to store the intermediate results.