BoardPath.java

packagecom.thealgorithms.dynamicprogramming;

publicfinalclassBoardPath {
privateBoardPath() {
 }

/**
 * Recursive solution without memoization
 *
 * @param start - the current position
 * @param end - the target position
 * @return the number of ways to reach the end from the start
 */
publicstaticintbpR(intstart, intend) {
if (start == end) {
return1;
 } elseif (start > end) {
return0;
 }
intcount = 0;
for (intdice = 1; dice <= 6; dice++) {
count += bpR(start + dice, end);
 }
returncount;
 }

/**
 * Recursive solution with memoization
 *
 * @param curr - the current position
 * @param end - the target position
 * @param strg - memoization array
 * @return the number of ways to reach the end from the start
 */
publicstaticintbpRS(intcurr, intend, int[] strg) {
if (curr == end) {
return1;
 } elseif (curr > end) {
return0;
 }
if (strg[curr] != 0) {
returnstrg[curr];
 }
intcount = 0;
for (intdice = 1; dice <= 6; dice++) {
count += bpRS(curr + dice, end, strg);
 }
strg[curr] = count;
returncount;
 }

/**
 * Iterative solution with tabulation
 *
 * @param curr - the current position (always starts from 0)
 * @param end - the target position
 * @param strg - memoization array
 * @return the number of ways to reach the end from the start
 */
publicstaticintbpIS(intcurr, intend, int[] strg) {
strg[end] = 1;
for (inti = end - 1; i >= 0; i--) {
intcount = 0;
for (intdice = 1; dice <= 6 && dice + i <= end; dice++) {
count += strg[i + dice];
 }
strg[i] = count;
 }
returnstrg[curr];
 }
}