DP solution: canJump[i] means from index 0, whether it can jump to index i
class Solution {
public boolean canJump(int[] nums) {
boolean[] canJump = new boolean[nums.length];
canJump[0] = true;
for (int i = 1; i < nums.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (canJump[j] && nums[j] >= i - j) {
canJump[i] = true;
break; // it's important to break here
}
}
}
return canJump[nums.length - 1];
}
}
另有 Greedy 解法。