BoardPath.java

packagesection19_DynamicProgramming;

publicclassBoardPath {

publicstaticvoidmain(String[] args) {
intn = 100000;
// int start = 0, end = n;
// System.out.println(boardPathRecursive(start, end)); // 492
// System.out.println(boardPathTopDown(start, end, new int[n]));
System.out.println(boardPathBottomUp(n));
System.out.println(boardPathBottomUpSpaceEfficient(n));
 }

// O(6^n) Time | Space - recursion extra space
publicstaticintboardPathRecursive(intstart, intend) {

if (start == end) {
return1;
 }
if (start > end) {
return0;
 }

intcount = 0;

for (intdice = 1; dice <= 6; dice++) {
count += boardPathRecursive(start + dice, end);
 }

returncount;
 }

// O(N) Time | O(N) Space + recursion extra space
// for large N, this will throw Stack overflow exception
publicstaticintboardPathTopDown(intcurrent, intend, int[] storage) {

if (current == end) {
return1;
 }
if (current > end) {
return0;
 }

if (storage[current] != 0) {
returnstorage[current];
 }

intcount = 0;

for (intdice = 1; dice <= 6; dice++) {
count += boardPathTopDown(current + dice, end, storage);
 }

storage[current] = count;

returncount;
 }

// O(N) Time | O(N) Space
publicstaticintboardPathBottomUp(intend) {
int[] storage = newint[end + 6];

storage[end] = 1;

for (intindex = end - 1; index >= 0; index--) {
storage[index] = storage[index + 1] + storage[index + 2] + storage[index + 3] + storage[index + 4]
 + storage[index + 5] + storage[index + 6];
 }

returnstorage[0];
 }

// O(N) Time | O(1) Space
publicstaticintboardPathBottomUpSpaceEfficient(intend) {

int[] storage = newint[6];

storage[0] = 1; // store

for (intslide = end - 1; slide >= 0; slide--) {
intsum = 0;
for (intidx = 5; idx > 0; idx--) {
sum += storage[idx];
storage[idx] = storage[idx - 1];
 }
sum += storage[0];
storage[0] = sum;
 }

returnstorage[0];
 }
}