1. LeetCode55题目链接链接

https://leetcode.com/problems/jump-game/

---

2. 结题思路（心酸之路）

开始理解的题目为，从第0位开会往后跳改位的值。然后只需要计算该位和下一位的值是不是0，以及是否超过边界就可以了。

/*
* 1. 首先判断下标是否等于数组长度
* 2. 计算下个位置的坐标
* 3. 计算下个位置的值
* 4. 若该值可以继续跳，则进行递归
*/
    public boolean canJump2Next(int position, int[] nums) {
        if (position == nums.length - 1) {
            return true;
        }
        int nextPos = position + nums[position];
        if (nextPos > nums.length - 1) {
            return false;
        } else {
            if (nums[nextPos] == 0) {
                return false;
            }
            if (canJump2Next(nextPos, nums)) {
                return true;
            }
        }
        return false;
    }

然后在信誓旦旦提交了，然后[2, 0]数组出错？！wtf？结果群里朋友借结了个图。。。。尴尬。

这是群友截得图哈哈哈，很尴尬

so...又进行了接下来的操作。修修改改。然后最终结果出现。。

/**
* 1. 同样先判断下标是否和长度相同，这里我多添加了一个判断如果第一位的值高于长度，可以直接为true
* 2.计算下个位置的坐标
* 3.取下个位置的坐标和数组长度两者之间的最小值
* 4.循环遍历从开始坐标的下一位一直到第三点两者之间的最小值之间的数据并进行比较。
*/
public static boolean canJump2Next(int position, int[] nums) {
        if (position == nums.length - 1 || nums[position] >= nums.length - 1) {
            return true;
        }
        int nextPos = position + nums[position];
        // 多次修改得出来的一句最精简的语句
        int minNum = Math.min(nextPos, nums.length - 1);
        for (int i = position + 1; i <= minNum; i++) {
            if (canJump2Next(i, nums)) {
                return true;
            }
        }
        return false;
    }

不要高兴的太早，这个方法还是有问题的，leetCode会有75次测试，第72次时候的数组为[2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6]，然而问题来了，这个长度的组数执行就已经使用了420ms。所以，第74测试的时候挂了！！因为第74次的时候已经有10W条数据了。

所以递归的方式走不通！！！

新方式来了！！！

看过大佬的思路，了解了一种贪心算法，在对问题求解时，做出在当前看来是最好的选择。就是说，不从整体最优上考虑，做出的只是在某种意义上的局部最优解。

思路：

采用一个变量来记录可以到达最远的坐标，最大所能达到的坐标比当前坐标还要小，说明当前坐标的值为0，不能继续往下跳，返回false，如果当前记录所能达到的最远坐标比数组长度还要长，直接返回true，不需要关心之后可以跳到哪里，这也是所谓的贪心算法，即使后面有更远的我们也不需要了。当然有些情况下，最后一次循环我们才能跳出，所以我们需要在循环外在判断下最大距离是否可以超过数组长度。

public static boolean canJump3Next(int[] nums) {
        if (nums == null) {
            return false;
        }
        if (nums.length <= 1) {
            return true;
        }
        int maxInstance = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (maxInstance < i) {
                return false;
            } else if (maxInstance >= nums.length - 1) {
                return true;
            }
            maxInstance = Math.max(maxInstance, nums[i] + i);
        }
        return maxInstance >= nums.length - 1;
    }