跳跃游戏II

来源Leetcode第45题跳跃游戏II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

自底向上的贪心

思路同跳跃游戏一题里一样，先用一个变量maxLength记录能到达的最远位置，再用变量end记录能到达的最远位置边界，steps记录步数。
则每当到达边界end的时候，将end更新为新的maxLength，并且steps++。
因为在一次遍历i 到 end 的时候，我们总能找到到达新的最远距离的方法。

提交的时候遇到坑了，在for循环里，i 是应该要小于 nums.length - 1的，少了末尾。因为在最开始第0个位置的时候，step已经加1了。如果是最后一步刚好到达末尾，steps并不用加1。如果是i < nums.length ，i到最后时进入if语句，steps会 + 1.

public int jump(int[] nums) {
    int maxLength = 0;
    int steps = 0;
    int end = 0;
    for(int i = 0 ; i < nums.length - 1; i++){
        maxLength = Math.max(maxLength, i + nums[i]);
        if(i == end){
            end = maxLength;
            steps++;
        }
    }
    return steps;
}

自顶向下的贪心

来自题解

我们知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。

至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的。

public int jump(int[] nums) {
    int position = nums.length - 1; //要找的位置
    int steps = 0;
    while (position != 0) { //是否到了第 0 个位置
        for (int i = 0; i < position; i++) {
            if (nums[i] >= position - i) {
                position = i; //更新要找的位置
                steps++;
                break;
            }
        }
    }
    return steps;
}