NC148：几步可以从头跳到尾

贪心算法：每次取局部最优解

解法1：从左向右逼近终点

一个记录当前位置，一个记录最远跳跃位置，一个记录跳跃次数，遍历数组（不需要遍历到最后一位，如果遍历到最后一位，那么正好跳到最后一位的时候就会多加一次跳跃次数），每当当前位置和索引i相等时（即当前位置最后一种跳法跳完时），将最远跳跃位置赋值给当前位置，跳跃次数加1；如果在索引中没找到当前位置，就说明已经跳出去了
1.然后从第一格到最后面n-1依次进行遍历,每经过之处都要求出最大可达到的位置maxStep;
2.如果index位置大于等于长度n,则表示已经跳出了;
3.如果index位置等于i,表示遍历到了最后一步跳法跳完时候,此时index需要更改一下为最远可以达到的位置,同时count需要进行加1,求出局部的最优

    public int Jump (int n, int[] A) {
        // write code here
        int count=0;//跳的步数
        int index=0;//当前位置
        int maxStep=0;//最远可跳跃位置
        for(int i=0;i<n-1;i++){
            maxStep=Math.max(maxStep,i+A[i]);//maxStep记录的每次可以达到的最大位置
            if(index>=n){
                break;//当前位置大于长度,表示已经跳完了,出去了
            }
            if(index==i){//当前位置等于i时候,表示遍历到了最后一步跳法跳完时候
                index=maxStep;//根据每处的maxStep,将当前位置换成局部最优的
                count++;//当前位置完成一步跳跃之后,等于最远可到达位置,步数加1
            }
        }
        return count;
    }

解法2：从右向左逼近起点

思路: 先确定终点位置, 从左至右找到第一个能到达终点(会不断更新)的位置, 以此类推, 逼近起点

 public int Jump (int n, int[] A) {
        // write code here
         int result = 0;
        // 初始化终点
        int reach = A.length - 1;
        // 逆推是否到达了起点
        while (reach != 0) {
            for (int i = 0; i < reach; i++) {
                // 从左(i递增)至右查找到第一个(离终点最远, 贪就贪在这里)能跳至终点的落脚处
                if (i + A[i] >= reach) {
                    // 更新终点
                    reach = i;
                    result++;
                }
            }
        }
        return result;
    }