题目地址：https://leetcode-cn.com/probl…题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1:输入: [2,3,1,1,4]输出: true解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。示例 2:输入: [3,2,1,0,4]输出: false解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。解答：解法一：动态规划。令dp[i]为跳到第i个位置是否可达。那么dp[0] = true。对于dpi如果在存在一个k(k>=0,k < i)使得dp[k] = true （即到k是可达的）并且 nums[k]+k>=i（从k可以跳到i）那么dp[i] = true。这个时间复杂度为O(N²)。java ac代码：class Solution { public boolean canJump(int[] nums) { boolean[]dp = new boolean[nums.length]; dp[0] = true; for(int i = 1;i < nums.length;i++) { for(int k = 0;k <= i-1;k++) if(dp[k]&&nums[k] >= i-k) { dp[i] = true; break; } } return dp[nums.length-1]; } }这个时间复杂度有点大，看了下面的提示这个题其实是贪心算法。那么如何用贪心算法来做呢？可以用一个max变量来维护当前能够到达的最远节点坐标，初始时max=nums[0]，即为0点能到达的最远节点。然后从1开始(i=1…nums.length-1)，如果max >= i代表能够到达i节点，如果nums[i] + i > max代表从这个点能够到达超过max的点，那么就更新max为nums[i] + i。这样一来每个节点只被访问一次，时间复杂度为O(N)。java ac代码：class Solution { public boolean canJump(int[] nums) { //max为当前最大可达的位置 int max = nums[0]; int len = nums.length; for(int i = 1;i <= max && i < len ;i++) if(nums[i] + i > max) max = nums[i]+i; return max >= nums.length-1; } }