70. Climbing Stairs

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?

Example: 1

Input: n = 2

Output: 2

Example: 2

Input: n = 3

Output: 3

Constraints:

• 1 <= n <= 45

Explanation of Approach:

• The first thing that you should see is that we can move 1 or 2 steps at a time.
• So, if there are N stairs, we can reach the N^th stair from (N-1)^th stair and (N-2)^th stair.
• So, if we calculate no of ways to get to (N-1)^th stair and (N-2)^th stair, we can get the number of ways to reach the N^th stair (i.e noOfWays(N - 1) + noOfWays(N - 2) = noOfWays(N)).
• Also handle the base case, which is N = 0, the 0^th stair can only be reached in one way since it is the starting point.
• Now you can code this recursively.

Using DP to make the code more efficient:

• Now if we use recursion, we will be computing many states again and again.
• This will lead to TLE.
• This can be shown by the following example.
• To compute noOfWays(5), we need to compute noOfWays(4) and noOfWays(3).
• To compute noOfWays(4), we need to compute noOfWays(3) and noOfWays(2).
• To compute noOfWays(3), we need to compute noOfWays(2) and noOfWays(1).
• Here we can notice that, noOfWays(3) and noOfWays(2) are being computed twice.
• If we had somehow bigger data, this would have resulted into TLE.
• So we will store the results of the subproblems.
• We will take the computed value of noOfWays(3) and store it in dp[3], and likewise for all 1 to N.
• All above things are explained through code below.
• Always remember, the result to a subproblem is obtained after the recursion from that state returns.

Full Code using Recursion (Java): class Solution { public int climbStairs(int n) { return recur(n); } int recur(int n) { if(n < 0) return 0; if(n == 0) return 1; return recur(n - 1) + recur(n - 2); } }

Full Code using DP (Java): class Solution { public int climbStairs(int n) { // making array dp to store subproblems int[] dp = new int[n + 1]; return recur(n, dp); } int recur(int n, int[] dp) { // handling base cases if(n < 0) return 0; if(n == 0) return 1; // reusing the value stored for this subproblem. if(dp[n] != 0) return dp[n]; // computing and storing the result of subproblem. // the dp[n] value is completely computed // after recur(n - 1, dp) and recur(n - 2, dp) return dp[n] = recur(n - 1, dp) + recur(n - 2, dp); return dp[n]; } }