public class JumpGameII {
/**
* 动态规划
*/
public int jump(int[] nums) {
int[] steps = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
steps[i] = i;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
steps[i] = Math.min(steps[i], steps[j] + 1);
}
}
}
return steps[nums.length - 1];
}
/**
* longestJump表示jumps步最远能到的距离
* maxJump表示以[0,i]为起点能覆盖到的最远距离
*/
public int jump2(int[] nums) {
int longestJump = 0, maxJump = 0, jumps = 0;
for (int i = 0; i < nums.length; i++) {
// 表示i-1时还覆盖得到，而i覆盖不到了，所以更新为[0,i-1]时的maxJump
if (longestJump < i) {
longestJump = maxJump;
jumps++;
}
maxJump = Math.max(maxJump, nums[i] + i);
}
return jumps;
}
}