题目地址：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]; }}