70. Climbing Stairs

Problem

Climbing Stairs - LeetCodeLeetCode

Intuition

It is a linear DP problem. The question asked is to find the number of unique ways to reach to "nth" step. From every step we can move forward "1" or "2" steps and should be inside the index limits.

Since they have asked for number of unique paths, we need to explore all the paths. To explore all the paths, we need to find a recursive way.

But using recursive way we might hit TLE as it does not scale with larger steps and the space will be a bottleneck. This because we might be calculating the same problem more than once, which is not needed.

Top Down

To solve this issue we can introduce a cache called dp arraywhere we can store the computed values.

Bottom Up

In this method, we start from 1st step and try to solve the problems for each cell what would be the number of unique paths at each cell and using that we will be solving till "nth" step

Time and SpaceComplexity

Approach	Time Complexity	Space Complexity
Tabulation with Space optimization (Bottom Up)	O(n)	O(1)
Tabulation (Bottom Up)	O(n)	O(n)
Memoization (Top Down)	O(n)	O(h) + O(n)
Recursive	$O(2^n)$	O(n)

Solution

class Solution {
    public int climbStairs(int n) {
        // Uncomment one of the helper methods based on the desired approach
        
        // return recursionHelper(n);

        // Memoization Approach
        // Since it starts from step 1, to make it easy we create dp[n+1] size
        // int[] dp = new int[n+1]; 
        // Arrays.fill(dp, -1); // Fill the values of row with "-1"
        // memoizationHelper(n, dp);
        // The final cell of dp array will have the reus;t
        // return dp[n]; // As it is a O-indexed array, we return dp[n]

    
        // return tabulationHelper(n);
        return tabulationSpaceOptimisedHelper(n);
    }

    // Tabulation approach with space optimization
    private int tabulationSpaceOptimisedHelper(int n) {
        // Time Compelxity: O(n), exploring all cells once
        // Space Complexity: O(1), no extra space is used

        // If we see the "tabulationHelper" method we can observe that we are 
        // making use of last two values only. As they are overlapping sub
        // problems the last two values results will hold the results of 
        // previous states also

        // Create an array to store the subproblem results
        int prev2 = 1; // Number of ways to climb 0 stairs
        int prev1 = 1; // Number of ways to climb 1 stair

        // Calculate the number of ways to climb each step up to n
        for (int i = 2; i <= n; i++) {
            int temp = prev1 + prev2; // Number of ways to climb the current step
            prev2 = prev1; // Update the number of ways for the previous 2 steps
            prev1 = temp; // Update the number of ways for the previous 1 step
        }

        return prev1; // Return the number of ways to climb n stairs
    }

    // Tabulation approach
    private int tabulationHelper(int n) {
        // Time Compelxity: O(n), exploring all cells once
        // Space Complexity: O(n), DP array is used to store sub problems results

        // Create an array to store the subproblem results
        int[] dp = new int[n + 1];

        // If we observe, the valid moves are "1" or "2" steps. But the for 1st
        // step you cannot reach it any other ways, same with 2nd step

        // Base cases
        dp[0] = 1; // Number of ways to climb 0 stairs
        dp[1] = 1; // Number of ways to climb 1 stair

        // Calculate the number of ways to climb each step up to n
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // Number of ways to climb the current step
        }

        return dp[n]; // Return the number of ways to climb n stairs
    }

    // Memoization approach
    private int memoizationHelper(int n, int[] dp) {
        // Time Compelxity: O(n), exploring all cells once
        // Space Complexity: O(h) + O(n), recursion stack + DP array

        // Base cases
        if (n == 0) {
            return 1; // Number of ways to climb 0 stairs
        }
        if (n < 0) {
            return 0; // Number of ways to climb negative stairs (invalid)
        }
        if (dp[n] != -1) {
            return dp[n]; // Return the already computed result
        }

        // Recursive calls to calculate the number of ways to climb n stairs
        int oneStep = memoizationHelper(n - 1, dp); // Number of ways to climb 1 step
        int twoStep = memoizationHelper(n - 2, dp); // Number of ways to climb 2 steps

        return dp[n] = oneStep + twoStep; // Store and return the computed result
    }

    // Recursive approach
    private int recursionHelper(int n) {
        // Time Compelxity: O(2^n), exploring all cells for each recursivly twice
        // Space Complexity: O(n), to store the values from recursive tree

        // Base cases
        if (n == 0) {
            return 1; // Number of ways to climb 0 stairs
        }
        if (n < 0) {
            return 0; // Number of ways to climb negative stairs (invalid)
        }

        // Recursive calls to calculate the number of ways to climb n stairs
        int oneStep = recursionHelper(n - 1); // Number of ways to climb 1 step
        int twoStep = recursionHelper(n - 2); // Number of ways to climb 2 steps

        return oneStep + twoStep; // Return the sum of the computed results
    }
}