### Leetcode: 70. Climbing Stairs (Memoization)

Climbing Stairs - An Optimized Dynamic Programming Solution

# 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.