Climbing Stairs

Thought Process

The Climbing Stairs problem demonstrates a classic dynamic programming pattern with overlapping subproblems. Here are two approaches to solve it efficiently:

Approach 1: Memoization (Top-Down) - Use recursion to break the problem into subproblems, but store results in an array to avoid redundant calculations. If n=1, return '1' (only one way to climb). If n=2, return '2' (two ways to climb). For larger 'n', recursively compute the sum of ways to reach (n-1) and (n-2) steps.

Approach 2: Tabulation (Bottom-Up) - Use an iterative approach to build the solution from base cases upwards. Initialize an array to store the number of ways to reach stair 1 & stair 2. For each step 'i', compute the sum of ways to reach (i-1) and (i-2).

Approach 1: Memoization (Top-Down)

class Solution {
public:
    int distinctWays[50]; // As maximum input size is 45
    int climbStairs(int n) {
        
        // Memoization
        if(n==1)
            return 1;
        else if (n==2)
            return 2;

        if(distinctWays[n] != 0)
            return distinctWays[n];
        else
            return distinctWays[n] = climbStairs(n-1) + climbStairs(n-2);
    }
};

Approach 2: Tabulation (Bottom-Up)

class Solution {
public:
    int climbStairs(int n) {
        
        int distinctWays[50]; // As maximum input size is 45

        // Base scenarios
        distinctWays[1]=1;
        distinctWays[2]=2;

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

Code Complexity

Time Complexity: O(n)

Both approaches compute the number of ways in linear time, as each step is processed once.

Space Complexity: O(n)

Both approaches use an array of size 'n' to store intermediate results.