共计 1128 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
解答：和第 55 题一样，首先试一下动态规划 dp[i] 代表到坐标为 i 的节点所用的最短步骤。那么 dp[0] = 0，dp[i] = min(dp[i-k]+1) , k >= 0 并且 k <= i-1, 并且 nums[k]+k >= i。不过可惜的是复杂度过大，为 O(N²)，用例不通过。
换一种思路，这个和第 55 题一样，这是个贪心问题，用一个 max 变量记录当前能够到达的最远节点。那么初始时 max = nums[0]，对于 i =1…nums.length-1，如果 nums[i]+i > max（即该节点能够到达比 max 更远的节点）就更新 max，并且把 dp[max+1]…dp[nums[i]+i] 更新为 dp[i]+ 1 否则跳过。这样一来，每一个节点只计算一次。也只访问一次，时间复杂度为 O(N)。
java ac 代码：
class Solution {
public int jump(int[] nums) {
int[]dp = new int[nums.length];
// 用这个最大值代替优先队列，因为效果是一样的
// 用优先队列保存已经求出的最大下标也可以，但是
// 每次都是从小到大求，所以每次求出更新 max 即可
// 保持是最大的，不需要使用优先队列。
int max = nums[0];
for(int i = 1;i < nums.length && i <= nums[0];i++)
{
dp[i] = 1;
}
for(int i = 1;i < nums.length;i++)
{
for(int k = max+1;k < nums.length&&k<=i+nums[i];k++)
{
dp[k] = dp[i]+1;
max = k;
}
}
return dp[nums.length-1];
}
}
动态规划超时代码：
class Solution {
public int jump(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 0;
for(int i = 1;i < nums.length;i++)
{
int temp = Integer.MAX_VALUE;
for(int k = i-1;k >= 0;k–)
if(nums[k] >= i-k)
temp = Math.min(temp,dp[k]);
dp[i] = temp+1;
}
return dp[nums.length-1];
}
}
