Dear Reader, this is the second problem in dp. I hope you have understood the basics of dp, we will solve more problems to make our understanding clear.
Important Links : Problem Link, Question Video
Prev Next
Climb Stairs
The most damaging phrase in the language is.. it's always been done this way
~ Grace Hopper
Climb Stairs
Problem Discussion :
- You are given a number n, representing the number of stairs in a staircase.
- You are on the 0th step and are required to climb to the top.
- In one move, you are allowed to climb 1, 2, or 3 stairs.
- You are required to print the number of different paths via which you can climb to the top.
Prerequisite:
Solve the Print Stairs Path before this, because we will only discuss the DP approach here.
Approach :1 (Recursion)
We have already seen the recursion approach in Print Stairs Path.
Approach :2 (Recursion + Memoization)
Let's first clear one thing, if there are
x ways to go from a to D
yways to go from b to D
z ways to go from c to D
Then for going from S to D we will have x+y+zapproaches.
We are going to use the same recursive code but just memoize the result at every instant. This will prevent the same calculations from being repeated again and again. You can draw the recursion tree and check for yourself. If you find difficulty understanding this part watch the video .
So we created an array, qb of size n+1, (because we will need to store the value of n as well, and if we create an array of size n we will have an index from 0 to n-1. Also, we will pass qb to each recursion call. There it will check if the value for n is already calculated. If so, then simply return, else recalculate it and store it before returning.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] qb = new int[n + 1];
int paths = countPaths(n, qb);
System.out.println(paths);
scn.close();
}
public static int countPaths(int n, int[] qb) {
if (n == 0) {
return 1;
} else if (n < 0) {
return 0;
}
if (qb[n] != 0) {
return qb[n];
}
int p1 = countPaths(n - 1, qb);
int p2 = countPaths(n - 2, qb);
int p3 = countPaths(n - 3, qb);
qb[n] = p1 + p2 + p3;
return p1 + p2 + p3;
}
}
java;
true";
Approach :3 (Tabulation)
In the case of the Tabulation method, we will first create an array of size n+1 so that we can access all the indexes from 0 to n.
- Create storage and assign a meaning to that storage.
We have already created storage. Now let's assign a meaning. For the i-th index, it will store the "number of ways to reach 0 from i" - Identify the direction of the problem.
We need to find where the smaller sub-problem lies, in the i-1 to 0 or i+1 to n region. For that, we can ask ourselves the following questions which are smaller problems.
- Finding paths between 0 to 0
- Finding paths between n to 0
- Travel and Solve.
Now we just iterate from the left side towards the right (this direction we already found before)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int paths = countPathsTab(n);
System.out.println(paths);
scn.close();
}
public static int countPathsTab(int n) {
if (n == 0) {
return 1;
} else if (n < 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (i >= 2)
dp[i] += dp[i - 2];
if (i >= 3)
dp[i] += dp[i - 3];
}
return dp[n];
}
}
java;
true";
Analysis
Time Complexity :
O(n)
Clearly, we are performing a loop of n iterations, and each iteration we are performing O(1) operations hence overall O(n).
This problem is very similar to Fibonacci except for the fact that we are using the last 3 instead of the last 2 in the case of Fibonacci.
SPACE COMPLEXITY :
O(n)
We are using a single array of size n+1 hence the space complexity is linear in nature. i.e O(n)
