从零学算法55-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法55。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

55.给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。文章来源地址https://www.toymoban.com/news/detail-832141.html

从一个点能否到达目标点根据两个方面判断，第一，该点与目标点的距离；第二，在该点能跳跃的长度，并且这两点影响力相同。
运用贪心的思想，我们定义最佳跳跃点为这两点因素综合起来最佳的点，也就是跳到目标点后剩余步数最大的点，比如例子 1 中 [2,3,1,1,4] 下标 1 的点跳到 target 后剩余 0 步，下标 3 的点同样如此，他们两个对于目标点 4 来说都是最佳跳跃点，而如果数组为 [2,3,1,2,4] 那么下标为 3 的点就是唯一的最佳跳跃点了，跳到 4 后还剩一步。跳跃能力好判断就是 nums[i] 越大越好，离目标点越近表示 i 越大，所以 i+nums[i] 越大表示它越是最佳跳跃点。
我们假设第一个点为最佳跳跃点，如果在之后能遇到更佳的并且我们可以从当前最佳跳跃点跳过去，我们就更新最佳跳跃点，直到遍历完整个数组，我们就找到了对最后一个点来说的最佳跳跃点，最终判断是否能从该点跳到目标点即可。
由于我们一直是保存着最佳跳跃点，所以如果我们从该最佳跳跃点不能到达某个点，那其他点更不用想了，这就是为什么我们最后找到的结果是对的，就像你想知道数组中是否存在数大于某个数 num，你会直接拿出数组最大数和 num 比

  public boolean canJump(int[] nums) {
      int index = 0;
      for(int i=1;i<nums.length;i++){
      	// 是否当前点更佳，记得一定要加 =，不然你可能到不了下一个最佳点了
          if(nums[i]+i>=index+nums[index] 
          // 能从 index 到 i
          && nums[index] >= i-index){
          	index = i;
          }
      }
      return nums[index] >= nums.length - 1 - index;
  }

动态规划：主要还是定义难，我们定义 dp[i] 为在 i 处最多能往后跳几步，那么 dp[i] 就好推了，如果它不在 i 处停留，就还剩 dp[i-1]-1 步，如果在 i 处停留，就还剩 nums[i] 步，max 一下即可。不过得特判一下数组长度为 1 和首位就只有 0 步的情况

  public boolean canJump(int[] nums) {
      if (nums.length == 1) {
          return true;
      }
      if(nums[0]==0)return false;
      int[] dp = new int[nums.length];
      dp[0] = nums[0];
      for(int i=1;i<nums.length;i++){
          dp[i]=Math.max(dp[i-1]-1,nums[i]);
          // 能直接到终点
          if(dp[i]>=nums.length-1-i)return true;
          // 后面的点都到不了了
          else if(dp[i]==0)return false;
      }
      return true;
  }