DP solution: canJump[i] means from index 0, the minimum steps it takes to jump to index i.
如果不加减枝会报TLE。
class Solution {
public int jump(int[] nums) {
int[] minJump = new int[nums.length];
minJump[0] = 0;
for (int i = 1; i < nums.length; i++) {
minJump[i] = Integer.MAX_VALUE - 1;
for (int j = 0; j < i; j++) {
if (nums[j] >= i - j) {
minJump[i] = Math.min(minJump[i], minJump[j] + 1);
if (minJump[i] == 1) {
break;
}
}
}
}
return minJump[nums.length - 1];
}
}
另有 Greedy 解法。贪心的规则就是在能够到达的范围之内，选择一个能够到达最远距离的点，更新步数，和更新最远到达的范围。