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 10¹⁰ +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:

1. 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.
2. 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