HACKER EARTH DYNAMIC PROGRAMMING SUPER TWO LETTER STRING

Question
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/super-two-letter-strings/description/

Two letter strings are the strings consisting of only two letters "X" and "Y". A string is "super two letter string" if

a) It does not have leading "X" letters.
b) It does not contain P consecutive "X" letters.

Your task is to find total number of Super two letter strings of length N.
Input :
The first line contains the number of test cases T . Each test case consists of two space separated integers - N and P .
Output :
For each test case output total number of Super two letter strings of length N modulo 1000000007(10^9+7).
Constraints :
1 <= T <= 100
1 <= N <= 10^4
1 <= P <= 10

SAMPLE INPUT

2
2 1
4 2

SAMPLE OUTPUT

1
5

Explanation

For first sample : Only possible string is : YY For second sample : Possible strings are : YXYX , YXYY, YYYX, YYXY, YYYY

Solution:

///I understood implementation from below submission

////https://www.hackerearth.com/submission/4264877/

package super_two_letter;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

///I understood implementation from below submission

////https://www.hackerearth.com/submission/4264877/

public class TestClass {

public static long MOD = 1000000007;

public static void main(String ar[]) throws IOException {

BufferedReader input = new BufferedReader(new InputStreamReader(

System.in));

int t = Integer.parseInt(input.readLine());

int MAX_NUMBER_OF_ROWS = 10005;//rows corresponding to length of the string

int MAX_COLUMNS = 12;// columns corresponding to consecutive "X" characters (I repeat consecutive X characters but not total no of X characters)

while (t-- > 0) 

{

int[][] dp = new int[MAX_NUMBER_OF_ROWS][MAX_COLUMNS];

String np[] = input.readLine().split(" ");

int n = Integer.parseInt(np[0]);

int p = Integer.parseInt(np[1]);

dp[1][0] = 1;//when we have string length ==1 then we can form only one  string that has ZERO consecutive   X i.e. we can have only 1 string i.e., Y

//dp[2][0] = 1;//when we have string length==2  then we can form only one  string that has ZERO consecutive   X i.e. we can have only 1 string i.e., YY

//out loop run through the rows i.e., the length of the string (length of string 1, length of string 2,length of string 3 .........)

for(int i=1;i<=n;i++)

{

//inner loop implies for each string of specific how many consecutive "X" as possible(i.e., how many have consecutive 0 X,

//consecutive 1 X  consecutive 2 X )

//limiting condition of inner loop is P we can go untill we have reached P-1 consecutive "X" character in each string of length i

for(int j=0;j<p;j++)

{

   

    //first column of every row means we can form a string of length i with zero consecutive "X" characters

//i.e., for length of 1 we can form total of 1 string with zero consecutive X ------> Y

//i.e., for length of 2 we can form total of 1 string with zero consecutive X ------> YY

   

//BELOW LINE MEANS WE CAN ADD Y CHARACTER TO NEXT LEVEL FROM EVERY STRING OF CURRENT LEVEL

//I.E., from YX you can go to YXY by adding Y

//from YY  you can go to YYY  by addig Y

               //hence we sum all the previous row elements for the next row first column (you can add a Y to each and every combination of string of  length i-1))

dp[i+1][0] = (int) ((dp[i+1][0]+dp[i][j])%MOD); 

//form Y you can go to X by adding Y

//from YY you can go to YYX by adding X

//but you cannot go to YXX from YX  if your P is 2 for example

if(j+1<p)//this statement checks the condition that did we reach p consecutive X characters. If yes we quit

{

//please refer the diagram to understand this condition more

dp[i+1][j+1] = (int) (dp[i][j]%MOD);

}

}

}

long total_no_of_Strings = 0;

for(int j=0;j<p;j++)

{

total_no_of_Strings +=dp[n][j];

}

System.out.println(total_no_of_Strings);

}

}

}

Please find below picture for comparing state table with recursion tree string formation.

Please update me if there are any errors or modifications .Thank you