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 {
    int[] waysToReach = new int[50];
    public int climbStairs(int n) {
        
        if(n==1 || n==2)
            return n;
        else if(waysToReach[n]!=0)
            return waysToReach[n];
        else
            return waysToReach[n] = climbStairs(n-1) + climbStairs(n-2);
    }
}

Approach 2: Tabulation (Bottom-Up)

class Solution {
    public int climbStairs(int n) {
        
        int[] waysToReach = new int[50];
        waysToReach[1] = 1;
        waysToReach[2] = 2;

        for(int i=3;i<=n;i++)
            waysToReach[i] = waysToReach[i-1] + waysToReach[i-2];

        return waysToReach[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.