共计 1011 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：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;
}
}
