如何使用最少的跳跃次数到达数组的最后一个位置?

给定一个非负整数数组，最初位于数组的第一个元素位置,数组中的每个元素代表你在该位置可以跳跃的最大长度,如何使用最少的跳跃次数到达数组的最后一个位置?

例如:数组array为:{2, 2, 3, 1, 2, 2, 1}

它可以3次跳完,

第一次,从起始位置2(array[0])跳到元素3(array[2]);

第二次,跳到元素2(array[5]);

第三次,跳到结尾1(array[6]).

首先分析一下

1. 当前元素值为跳跃的最大长度,在没有任何前提支持下的最合适值就是元素最大值.

2. 在这个最大的跳跃范围内,需要选取一个合适值,保证下次跳跃能达到最大距离.

3. 通过上面的分析,我们发现需要3个指针

慢指针,指向当前已选择元素所在位置.

快指针,指向当前元素能跳跃到的最大位置,quickIndex=array[slowIndex] + slowIndex;并作为下次的慢指针.

最大移步指针,用来查找本次跳跃范围内,指向下一次跳跃后,达到的最大距离所在元素位置;并作为下次跳跃的快指针.

按这个思路,我们一起分析下,上面数组是如何跳跃的.

1. 起始状态

2. 根据slow指针指向的元素值,quick指针应该移动到array[2]

3. 确定好快慢指针范围,再来查找在这个范围内能跳越到的最大距离:

元素值 + 索引值 = 该元素跳跃最大索引值

array[1] + 1 = 3

Array[2] + 2 = 5

最大移步指针指向5

4. 确定好下一次能跳到的最大距离,重新调整快慢指针.

5. 再次确定最大移步指针

6. 移步指针已经指向数组结尾,跳跃结束.算上快慢指针的第一次合理定位,一共需要3次跳跃就能到达数组尾部.

通过上述流程,可以发现当我们不能从整体上给出一个最优方案时,可以只根据当前状态给出最好选择,做出局部意义上的最优解. 这种问题求解的思路叫做贪心算法.

附上代码:

 int jump(int[] nums) {
        int count = 0;
        int length = nums.length;
        int slowIndex = 0;
        int quickIndex = 0;
        while (quickIndex < length - 1) {
            count++;
            int nextIndex = slowIndex;
            for (int i = slowIndex; i <= quickIndex; i++) {
                if (nums[i] + i > nextIndex) {
                    nextIndex = nums[i] + i;
                }
            }
            slowIndex = quickIndex;
            quickIndex = nextIndex;
        }
        return count;
    }