55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Solution:
public class Solution { public boolean canJump(int[] nums) { int reachable= 0; for (int i = 0; i < nums.length; i++) { if (i > reachable) return false; reachable = Math.max(reachable, i + nums[i]) } return true; } }
the basic idea is this: at each step, we keep track of the furthest reachable index. The nature of the problem (eg. maximal jumps where you can hit a range of targets instead of singular jumps where you can only hit one target) is that for an index to be reachable, each of the previous indices have to be reachable.
Hence, it suffices that we iterate over each index, and If we ever encounter an index that is not reachable, we abort and return false. By the end, we will have iterated to the last index. If the loop finishes, then the last index is reachable.
九章算法答案：
Greedy:
public class Solution { public boolean canJump(int[] A) { // think it as merging n intervals if (A == null || A.length == 0) { return false; } int farthest = A[0]; for (int i = 1; i < A.length; i++) { if (i <= farthest && A[i] + i >= farthest) { farthest = A[i] + i; } } return farthest >= A.length - 1; } }
Dynamic Pro:
// 这个方法，复杂度是 O(n^2) 可能会超时，但是依然需要掌握。 public class Solution { public boolean canJump(int[] A) { boolean[] can = new boolean[A.length]; can[0] = true; for (int i = 1; i < A.length; i++) { for (int j = 0; j < i; j++) { if (can[j] && j + A[j] >= i) { can[i] = true; break; } } } return can[A.length - 1]; } }
原文：http://www.cnblogs.com/licybupt/p/6380275.html