GeezerVison is showing github.com — Java/DynamicProgramming/BoardPath.java at master · siva87/Java

Expand file tree

BoardPath.java

Copy path

More file actions

Latest commit

History

75 lines (65 loc) · 1.73 KB

BoardPath.java

Copy path

File metadata and controls

75 lines (65 loc) · 1.73 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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];

}