Climbing stairs

How to Identify a DP problem:

When encountering a problem, it's crucial to recognize if it can be approached using dynamic programming (DP) techniques. This is especially relevant when the problem exhibits certain characteristics that align with the strengths of dynamic programming. Some common indicators that suggest a problem might be suitable for dynamic programming include:

Problem asking for count the total number of ways.
Given multiple ways of performing a task, it is asked which way will yield the minimum or maximum output.

If the question asks for either of the above two points mentioned earlier, recursion can be applied to attempt solving the problem. Once the recursive solution is obtained, it can be converted into a dynamic programming approach.

Observation:

The problem statement asks to count the total ways one can jump from the 0th step to the nth step by jumping either 1 or 2 steps at a time. Since the question requires counting total ways, recursion can be applied, and eventually, this problem can also be solved using dynamic programming.

How to write ruccurence relation:

Once the problem has been identified, the following three steps comes handy in solving the problem:

Try to represent the problem in terms of indexes.
Try all possible choices/ways at every index according to the problem statement.
If the question states "count all the ways," then the sum of all choices/ways should be returned. If the question asks to find "the maximum/minimum", then the choice/way with the maximum/minimum output should be returned.

Solution using recursion:

In recursion, top-down approach is followed, so try getting the answer that is required, then go to the base case and come back.
To represent the problem in terms of indices, assume n stairs as indices from 0 to N. The recusive call will basically return all the ways to reach the nth step.

In order to consider all possible actions at an index, the choices available are either to jump 1 step or 2 steps, so proceed accordingly.

Now, to count all the ways, return the sum of all the choices in our recursive function.

/*It is pseudocode and not tied to 
any specific programming language.*/
f(n){
      oneStep = f(n-1)
      twoStep = f(n-2)
      return oneStep + twoStep
}

The base case would be, when the N = 0, it means, the starting and ending steps are same. So, there is just one way possible and that will be to stand there as it is.
Edge case: When N = 1 and f(N-2) has been called, we will reach stair -1, which is not a valid stair. Therefore, an additional edge case is added to return 1 (the only way) when N = 1.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to count total ways to reach nth stair
    int climbStairs(int n) {
        // Base case
        if (n == 0) return 1;
        if (n == 1) return 1;
        
        // Taking 1 step at a time
        int oneStep = climbStairs(n-1);
        
        // Taking 2 steps at a time
        int twoSteps = climbStairs(n-2);
        
        // Return total ways
        return oneStep + twoSteps;
    }
};

int main() {
    int n = 3;
    
    // Create an instance of Solution class
    Solution sol;
    
    // Print the answer
    cout << "The total number of ways: " << sol.climbStairs(n) << endl;
    
    return 0;
}
import java.util.*;

class Solution{
    //Function to count total ways to reach nth stair
    public static int climbStairs(int n){
        //Base case
        if(n == 0) return 1;
        if(n == 1) return 1;
        
        //Taking 1 step at a time
        int oneStep = climbStairs(n-1);
        
        //Taking 2 steps at a time
        int twoSteps = climbStairs(n-2);
        
        //Return total ways
        return oneStep+twoSteps;
    }
	public static void main (String[] args){
        int n = 3;
        
        //Create an instance of Solution class
        Solution sol = new Solution();
        
        //Print the answer
        System.out.println("The total number of ways: "+sol.climbStairs(n));
	}
}
class Solution:
    # Function to count total ways to reach nth stair
    def climbStairs(self, n):
        # Base case
        if n == 0:
            return 1
        if n == 1:
            return 1
        
        # Taking 1 step at a time
        oneStep = self.climbStairs(n-1)
        
        # Taking 2 steps at a time
        twoSteps = self.climbStairs(n-2)
        
        # Return total ways
        return oneStep + twoSteps

if __name__ == "__main__":
    n = 3
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the answer
    print("The total number of ways:", sol.climbStairs(n))
class Solution {
    // Function to count total ways to reach nth stair
    climbStairs(n) {
        // Base case
        if (n === 0) return 1;
        if (n === 1) return 1;
        
        // Taking 1 step at a time
        let oneStep = this.climbStairs(n-1);
        
        // Taking 2 steps at a time
        let twoSteps = this.climbStairs(n-2);
        
        // Return total ways
        return oneStep + twoSteps;
    }
}

    let n = 3;
    
    // Create an instance of Solution class
    let sol = new Solution();
    
    // Print the answer
    console.log("The total number of ways:", sol.climbStairs(n));

Complexity Analysis:

Time Complexity: O(2^N), where N is the given number of stairs. The number of recursive calls roughly follows a Fibonacci-like sequence, where climbStairs(n) is approximately 2^N. This is because each call branches into two more calls, leading to an exponential growth in the number of calls.

Space Complexity:The space complexity of this recursive approach is O(n). This is because the maximum depth of the recursion stack can go up to n, due to the linear nature of the stack usage relative to the input size n.

Memoization approach:

As, the recursive solutions recalculate the same subproblems again and again, leading to inefficiencies, especially with larger inputs. Memoization addresses this by storing the results of already computed subproblems.

When a subproblem is encountered again, which is known as overlapping subproblem, instead of recalculating it, the precomputed result is simply retrieved from memory. This speeds up the computation and also reduces the time complexity significantly, often transforming an exponential-time recursive solution into a polynomial-time solution.

Memoization tends to store the value of subproblems in some map/ table. As, here we have only one parameter in recursive function, so we can create an 1D array to store the values of subproblems.

Declare an Array dp[] of Size n+1: Here, n is the parameter or size of the problem, as the highest number of subproblems can be n+1(including 0 as well). It represents the solution to the subproblem for any given index. Initially, fill the array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    //Helper function to apply memoization
    int func(int n, vector<int> &dp) {
        // Base condition
        if (n <= 1) {
            return 1;
        }
        
        // Check if the subproblem is already solved
        if (dp[n] != -1) {
            return dp[n];
        }
        
        // Return the calculated value
        return dp[n] = func(n-1, dp) + func(n-2, dp);
    }
    
public:
    // Function to count total ways to reach nth stair
    int climbStairs(int n) {
        // Initialize dp vector with -1
        vector<int> dp(n + 1, -1); 
        
        return func(n, dp);
    }
};

int main() {
    int n = 5;
    
    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "The total number of ways: " << sol.climbStairs(n) << endl;

    return 0;
}
import java.util.*;

class Solution {
    //Helper function to apply memoization
   private int func(int n, int dp[]){
        //Base condition
        if (n <= 1) {
            return 1;
        }
        
        //Check if the subproblem is already solved
        if (dp[n] != -1) {
            return dp[n];
        }
        
        //Return the calculated value
        return dp[n] = func(n-1, dp) + func(n-2, dp);
    }
    // Function to count total ways to reach nth stair
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        
        // Initialize dp array with -1
        Arrays.fill(dp, -1);
        
        // Return the calculated value
        return dp[n] = func(n, dp);
    }
    
    public static void main(String[] args) {
        int n = 5;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the answer
        System.out.println("The total number of ways: " + sol.climbStairs(n));
    }
}
class Solution:
    #Helper function to apply memoization
    def func(self, n, dp):
        # Base condition
        if n <= 1:
            return 1
        
        # Check if the subproblem is already solved
        if dp[n] != -1:
            return dp[n]
        
        # Return the calculated value
        dp[n] = self.func(n-1, dp) + self.func(n-2, dp)
        return dp[n]
        
    # Function to count total ways to reach nth stair
    def climbStairs(self, n):
        # Initialize dp array with -1
        dp = [-1] * (n + 1) 
        
        return self.func(n, dp)
        

if __name__ == "__main__":
    n = 5
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the answer
    print("The total number of ways:", sol.climbStairs(n))
class Solution {
    func(n, dp){
        // Base condition
        if (n <= 1) {
            return 1;
        }
        
        // Check if the subproblem is already solved
        if (dp[n] !== -1) {
            return dp[n];
        }
        
        // Return the calculated value
        dp[n] = this.func(n-1, dp) + this.func(n-2, dp);
        return dp[n];
    }
    // Function to count total ways to reach nth stair
    climbStairs(n) {
        // Initialize dp array with -1
        let dp = Array(n+1).fill(-1);
        
        return this.func(n, dp);
    }
}
let n = 5;
    
// Create an instance of Solution class
let sol = new Solution();
    
// Print the answer
console.log("The total number of ways: " + sol.climbStairs(n));

Complexity Analysis:

Time Complexity: O(N), where N is the given number of stairs. This is because we perform a linear number of operations relative to the input size n.

Space Complexity:O(N)+O(N), We are using a recursion stack space O(N) and an array (again O(N)). Therefore total space complexity will be O(N) + O(N) ≈ O(N).

Tabulation approach:

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Bottom-Up Approach in Tabulation: Tabulation involves solving a problem by building a solution from the bottom up. This means start with the smallest subproblems and iteratively compute solutions for larger subproblems until the desired solution has been found.
Declare an Array dp[] of Size n+1: Here, n is the parameter or size of the problem. It represents the solution to the subproblem for any given index.
Setting Base Cases in the Array:In the recursive code, we knew the answer for base cases, similarly if we are computing in tabulation, we definitely know that the answer for dp[0] = 0 and dp[1] = 1.
Iterative Computation Using a Loop: Set an iterative loop that traverses the array( from index 2 to n). To compute the solution for larger values, use a loop that iterates from the smallest subproblem up to n. The current value(dp[i]) represents the subproblem and by the recurrence relation it is obvious that it is sum of previous two values, for every index(i) set its value as dp[i-1] + dp[i-2].
Returning the last element: The last element of the dp array is returned because it holds the optimal solution to the entire problem after the bottom-up computation has been completed.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to count total ways to reach nth stair
    int climbStairs(int n) {
        //Declare dp array of size n+1
        vector<int> dp(n + 1, -1);

        //Insert the values of base conditions
        dp[0] = 1;
        dp[1] = 1;
        
        //Iterate and update every index of dp array
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        //Return the answer
        return dp[n];

    }
};

int main() {
    int n = 3;

    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "The total number of ways: " << sol.climbStairs(n) << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to count total ways to reach nth stair
    public int climbStairs(int n) {
        // Declare dp array of size n+1
        int[] dp = new int[n + 1];

        // Insert the values of base conditions
        dp[0] = 1;
        dp[1] = 1;

        // Iterate and update every index of dp array
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // Return the answer
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 3;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Print the answer
        System.out.println("The total number of ways: " + sol.climbStairs(n));
    }
}
class Solution {
    // Function to count total ways to reach nth stair
    climbStairs(n) {
        // Declare dp array of size n+1
        let dp = new Array(n + 1).fill(-1);

        // Insert the values of base conditions
        dp[0] = 1;
        dp[1] = 1;

        // Iterate and update every index of dp array
        for (let i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // Return the answer
        return dp[n];
    }
}

    let n = 3;

    // Create an instance of Solution class
    let sol = new Solution();

    // Print the answer
    console.log("The total number of ways:", sol.climbStairs(n));

class Solution {
    // Function to count total ways to reach nth stair
    climbStairs(n) {
        // Declare dp array of size n+1
        let dp = new Array(n + 1).fill(-1);

        // Insert the values of base conditions
        dp[0] = 1;
        dp[1] = 1;

        // Iterate and update every index of dp array
        for (let i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // Return the answer
        return dp[n];
    }
}

    let n = 3;

    // Create an instance of Solution class
    let sol = new Solution();

    // Print the answer
    console.log("The total number of ways:", sol.climbStairs(n));

Complexity Analysis:

Time Complexity: O(N), where N is the given number of stairs. This is because we perform a linear number of operations relative to the input size N.

Space Complexity:O(N), an additional array dp of size n + 1 is used to store intermediate results. Hence, the space complexity is O(N).

Space Optimization:

If we observe the relation dp[i] = dp[i-1] + dp[i-2], we notice that to calculate the current value at index i, we only need the previous two values. Using an entire array for just two values seems overhead. Instead, the work can be done using two variables to store the previous two values, achieving O(1) space complexity. In each iteration, the current value and the variables containing previous values can be updated.

In each iteration, cur_i is calculated and prev and prev2 are updated to become the next iteration's prev and prev2 respectively.
After the iterative loop has ended, prev is returned as the answer.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to count total ways to reach nth stair
    int climbStairs(int n) {
        /*Initialize two variables to 
        store previous results*/
        int prev2 = 1;
        int prev = 1;
        
        //Iterate and update the variables
        for (int i = 2; i <= n; i++) {
            int cur_i = prev2 + prev;
            prev2 = prev;
            prev = cur_i;
        }
        //Return the answer as prev
        return prev;

    }
};

int main() {
    int n = 3;

    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "The total number of ways: " << sol.climbStairs(n) << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to count total ways to reach nth stair
    public int climbStairs(int n) {
        /*Initialize two variables to 
        store previous results*/
        int prev2 = 1;
        int prev = 1;
        
        //Iterate and update the variables
        for (int i = 2; i <= n; i++) {
            int cur_i = prev2 + prev;
            prev2 = prev;
            prev = cur_i;
        }
        //Return the answer as prev
        return prev;
    }

    public static void main(String[] args) {
        int n = 3;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Print the answer
        System.out.println("The total number of ways: " + sol.climbStairs(n));
    }
}
class Solution:
    # Function to count total ways to reach nth stair
    def climbStairs(self, n):
        """Initialize two variables to 
        store previous results"""
        prev2 = 1;
        prev = 1;
        
        #Iterate and update the variables
        for i in range(2, n+1):
            cur_i = prev2 + prev;
            prev2 = prev;
            prev = curr;
    
        #Return the answer as prev
        return prev;

if __name__ == "__main__":
    n = 3

    # Create an instance of Solution class
    sol = Solution()

    # Print the answer
    print("The total number of ways:", sol.climbStairs(n))
class Solution {
    // Function to count total ways to reach nth stair
    climbStairs(n) {
        /*Initialize two variables to 
        store previous results*/
        let prev2 = 1;
        let prev = 1;
        
        //Iterate and update the variables
        for (let i = 2; i <= n; i++) {
            let cur_i = prev2 + prev;
            prev2 = prev;
            prev = curr;
        }
        //Return the answer as prev
        return prev;
    }
}

    let n = 3;

    // Create an instance of Solution class
    let sol = new Solution();

    // Print the answer
    console.log("The total number of ways:", sol.climbStairs(n));

Complexity Analysis:

Time Complexity: O(N), where N is the given number of stairs. This is because we perform a linear number of operations relative to the input size n.

Space Complexity:O(1). As no extra space is being used here.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

How to Identify a DP problem:

Observation:

How to write ruccurence relation:

Solution using recursion:

Complexity Analysis:

Memoization approach:

Complexity Analysis:

Tabulation approach:

Complexity Analysis:

Space Optimization:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code