Jumping frog problem

Problem

There were n stones across a river. Each stone was places 1 meter apart. A frog can jump in steps of 1 meter, 2 meters, 3 meters and so on. The first jump is always 1 meter. The typical behavior of the frog is such that if it goes k meters in one jump then on its next jump it can go either k-1, k or k+1 meters. It won't jump backward. So when there were n stones across the river it could cross the river. Let's take n=10; and initial position of the frog is 0.
Some possible paths could be
1, 2, 3, 4, 6, 9, 10
1, 3, 6, 10
1, 2, 4, 7, 10
Now some of the stones across the river have been removed. Find the algorithm to figure out whether the frog would be able to cross the river after removing those stones. For example, as the frog always takes the first jump for 1 meter. If the first stone is removed then it will never be able to cross the river.Solution

Solution description

Solution

If the frog somehow reaches an intermediate stone m and his last jump was for k meters. Then his next location can be m+k-1, m+k or m+k+1 (Jump can't be 0 or negative, so those cases will be ignored). So we can create a subproblem of reaching from m to the end. As we start with initial position 0 and initial jump 1, for different branches the same value of m and k can appear multiple times. As we have overlapping subproblems we can use dynamic problem. We can use a two dimensional array to store result for different m and k values for memoization of the repeated subproblems. 

Code

import java.util.ArrayList;
import java.util.List;

public class FrogJump {

 public static void main(String[] args) {
  boolean[] stone = { true, false, true, true, true, false, true, false,
    true, false, true, true, false, true };
  System.out.println("Frog jump " + frogJump(stone));
 }

 static List frogJump(boolean[] stone) {
  int[][] jumpTable = new int[stone.length + 1][stone.length + 1];
  if (frogJump(stone, 1, 0, jumpTable)) {
   List result = new ArrayList();
   int currentStone = 0;
   int jump = 1;
   while (currentStone < stone.length) {
    result.add(currentStone);
    jump = jumpTable[currentStone][jump];
    currentStone += jump;
   }
   result.add(stone.length);
   return result;
  }
  return null;
 }

 static boolean frogJump(boolean[] stone, int jump, int currentLocation,
   int[][] jumpTable) {
  if (currentLocation >= stone.length
    || jumpTable[currentLocation][jump] != 0)
   return true;
  if (jump < 1 || !stone[currentLocation])
   return false;
  for (int i = 1; i > -2; --i) {
   if (frogJump(stone, jump + i, currentLocation + jump + i, jumpTable)) {
    jumpTable[currentLocation][jump] = jump + i;
    return true;
   }
  }
  return false;
 }
}