Davis Staircase Problem in Java
Davis has several stairs in his home and prefers to ascend one, two, or three steps at a time. As a highly clever youngster, he thinks about how many ways it can reach the top of the staircase.
Considering R the heights of each of his house's stairs, calculate and display the total number of ways he may climb every staircase, module 1010 +7 on a new line.
Example
P= 5
This staircase comprises five steps. Davis may take the steps listed below in the following order:
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2
There are 13 possible outcomes for these five steps, and 13 modulo 10000000007 = 13.
Explanation of the Function
Within the editor below, replace the stepPerms function utilizing recursion.
The following parameters are available in stepPerms:
int P: number of stairs in the staircase
Returns
int: total number of ways Davis may climb the stairs modulo 10000000007
Format of Input
The first line includes a single integer, R, that signifies the number of staircases inside his home.
Each of the R lines that follows has a single integer, P, representing the height of staircase u.
Constraints
1 ≤ R ≤ 5
1 ≤ P ≤ 36
Subtasks
1 ≤ P ≤ 20 for the 50% highest possible score.
Input Sample
STDIN Function
----- --------
3 R = 3 (number of staircases)
1 first staircase P = 1
3 second P = 3
7 third P = 7
Output Sample
1
4
44
Explanation
Let us count the total number of approaches to ascend the first two Davis's=3 staircases:
- Since the first staircase only has a P=1 step, there is just one method by which he can ascend it (i.e., by jumping 1 step). As a result, we display 1 on a new line.
- This second staircase contains P=3 stairs, and he may ascend it in one of four ways:
1 → 1 → 1
1 → 2
2 → 1
3
As a result, we print 4 on a new line.
Filename: DavisStaircase.java
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class DavisStaircase {
public static class Matrix{
static int P;
public Matrix(int P)
{
this.P=P;
}
static long[][] multiply(long[][] x ,long[][] y)
{
long[][] ans=new long[P][P];
for(int u=0;u<P;u++)
for(int v=0;v<P;v++){
ans[u][v]=0;
for(int w=0;w<P;w++)
ans[u][v]+=x[u][w]*y[w][v];
}
return ans;
}
static void print(long[][] x)
{
for(int u=0;u<P;u++)
{
for(int v=0;v<P;v++)
System.out.print(x[u][v]+" ");
System.out.println();
}
}
//Matrix Exponentiation
static long MatrixExpo(long[][] base ,int power )
{
// print(base);
//base cases
if(power<=0) return 0;
if(power==1) return 1;
if(power==2) return 2;
if(power==3) return 4;
power-=3;
long[][] ans=new long[P][P];
//Make Answer-matrix
for(int u=1;u<P;u++)
for(int v=0;v<P;v++) ans[u][v]=0;
ans[0][0]=4;ans[0][1]=2;ans[0][2]=1;
//Left-handside matrix
//4 2 1
//0 0 0
//0 0 0
while(power>0)
{
if(power%2==1)
ans=multiply(ans ,base);
power=power/2;
base=multiply(base ,base);
}
//return final answer F(P)
return ans[0][0];
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int R = in.nextInt();
long[][] Q=new long[3][3];
//1 1 0
//1 0 1
//1 0 0
Q[0][0]=Q[1][0]=Q[2][0]=1;Q[0][1]=1;Q[0][2]=0;
Q[1][1]=0;Q[1][2]=1;Q[2][1]=0;Q[2][2]=0;
for(int x0 = 0; x0 < R; x0++){
int P = in.nextInt();
Matrix mat= new Matrix(3);
System.out.println(Matrix.MatrixExpo(Q ,P));
}
}
}
Input
3
1
3
7
Output
1
4
44
Filename: DavisStaircase.java
import java.util.*;
public class DavisStaircase {
public static int numWays(int P) {
if (P < 3) {
return P;
}
if (P == 3) {
return 4;
}
int[] numWays = new int[P];
numWays[0] = 1; //finding the number of ways.
numWays[1] = 2; //finding the number of ways.
numWays[2] = 4; //finding the number of ways.
for (int u = 3; u < P; u++) {
numWays[u] = numWays[u - 1] + numWays[u - 2] + numWays[u - 3];
}
return numWays[P - 1];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int P = in.nextInt(); // initializing the value.
while (in.hasNext()) { // checking the while condition.
int staircaseHeight = in.nextInt();
System.out.println(numWays(staircaseHeight));
}
}
}
Input
2
5
8
Output
13
81