leetcode_【55】跳跃游戏

1.题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

2.解题思路

方法1：动态规划

从左到右依次判断索引坐标i是否能跳到，当遍历到数组末尾时，当dp[nums.length-1]==true时说明能跳到这个位置。即可以跳到最后一个位置。

方法2: 贪心算法

从右向左迭代，对于每个节点我们检查是否存在一步跳跃可以到达 GOOD 的位置（currPosition + nums[currPosition] >= leftmostGoodIndex）。

如果可以到达，当前位置也标记为 GOOD ，同时，这个位置将成为新的最左边的 GOOD 位置，一直重复到数组的开头，如果第一个坐标标记为 GOOD 意

味着可以从第一个位置跳到最后的位置。

3.代码

方法1：动态规划

public static boolean canJump(int[] nums) {

      if(nums==null)
          return false;
      boolean []dp = new boolean[nums.length];
      dp[0] = true;
      for(int i = 1;i<nums.length;i++){
          for(int j = 0;j<i;j++){
              //如果之前j节点可达，并且从此节点可以跳到i
              if(dp[j] && nums[j]+j>=i){
                  dp[i] = true;
                  break;
              }
          }
      }
      return dp[nums.length-1];
   }

方法2：贪心算法

public static boolean canJump2(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }

4.提交记录

方法1：动态规划

![leetcode提交结果]

(https://github.com/qiulig/IMG/raw/master/55-1.jpg)

方法2：贪心算法

![leetcode提交结果]

(https://github.com/qiulig/IMG/raw/master/55-2.jpg)