JumpGame.java

package leetcode;


public class JumpGame {

  public boolean canJumpFromPosition(int position, int[] nums) {
    if (position == nums.length - 1) {
      return true;
    }

    int furthestJump = Math.min(position + nums[position], nums.length - 1);
//         Old
//        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++)
// New
    for (int nextPosition = furthestJump; nextPosition > position; nextPosition--) {
      if (canJumpFromPosition(nextPosition, nums)) {
        return true;
      }
    }

    return false;
  }

  public boolean canJump(int[] nums) {
//        return canJumpFromPosition(0, nums);
    int lastPos = nums.length - 1;
    for (int i = nums.length - 1; i >= 0; i--) {
      if (i + nums[i] >= lastPos) {
        lastPos = i;
      }
    }
    return lastPos == 0;
  }
}