package DynamicProgramming;
/*
* this is an important Algo in which
* we have starting and ending of board and we have to reach
* we have to count no. of ways
* that help to reach end point i.e number by rolling dice
* which have 1 to 6 digits

Test Case:
here target is 10

int n=10;
		startAlgo();
		System.out.println(bpR(0,n));
		System.out.println(endAlgo()+"ms");
		int[] strg=new int [n+1];
		startAlgo();
		System.out.println(bpRS(0,n,strg));
		System.out.println(endAlgo()+"ms");
		startAlgo();
		System.out.println(bpIS(0,n,strg));
		System.out.println(endAlgo()+"ms");



*/
public class BoardPath {
 public static long startTime;
 public static long endTime;

 public static void startAlgo() {
 startTime = System.currentTimeMillis();
 }

 public static long endAlgo() {
 endTime = System.currentTimeMillis();
 return endTime - startTime;
 }

 public static int bpR(int start, int end) {
 if (start == end) {
 return 1;
 } else if (start > end) return 0;
 int count = 0;
 for (int dice = 1; dice <= 6; dice++) {
 count += bpR(start + dice, end);
 }
 return count;
 }

 public static int bpRS(int curr, int end, int strg[]) {
 if (curr == end) {
 return 1;
 } else if (curr > end) return 0;
 if (strg[curr] != 0) return strg[curr];
 int count = 0;
 for (int dice = 1; dice <= 6; dice++) {
 count += bpRS(curr + dice, end, strg);
 }
 strg[curr] = count;
 return count;
 }

 public static int bpIS(int curr, int end, int[] strg) {
 strg[end] = 1;
 for (int i = end - 1; i >= 0; i--) {
 int count = 0;
 for (int dice = 1; dice <= 6 && dice + i < strg.length; dice++) {
 count += strg[i + dice];
 }
 strg[i] = count;
 }
 return strg[0];
 }
}