跳跃游戏

在跳跃游戏中，要明白贪心法则的定义。贪心法则：最基本的理解就是，每次选择当前最优的解，到最后就能得到整个问题的最优解法。

1.题目

给定数组arr，arr[i]=k代表可以从位置i向右跳1~k个距离。比如，arr[2] == 3，代表从位置2可以调到位置3、位置4或位置5。如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。

2.举例

arr = {3,2,3,1,1,4}

arr[0]==3，选择跳到位置2：arr[2]==3，可以跳到最后的位置。所以返回2.

3.解题思路（利用贪心法则）

具体过程如下：

• 1.整形变量jump，代表目前跳了多少步。（就是跳了几次，就是题目要求的值）。整形变量cur，代表如果只能跳jump步，最远能够到达的位置。（换句话说，按照上面的例子：假如你jump一次，从0位置开始a[0]==3，则你可以到达的最远的位置就是1,2,3）。整型变量next，代表如果在多跳一步，最远能够到达的位置。初始时，jump=0，cur=0，next=0.

image.png

2.从左到右遍历arr，假设遍历到位置i。

• 2.1如果cur>=i，说明jump步可以达到位置i，此时什么也不做。
• 2.2如果cur<i，说明只跳jump不能到达位置i，需要多跳一步才行。此时令jump++，cur=next。表示多跳了一步，cur更新成jump+1步能够到达的位置，即next。
• 2.3将next更新成next = Math.max(next,i+arr[i]);表示下一次多跳一步到达的最远位置。

3.当遍历到arr的尾部时，最终返回jump即可。

image.png

4.具体代码如下

/**
 * @author zhoujian123@hotmail.com 2018/8/15 15:53
 */
public class JumpGame {

    public static int jump(int [] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //代表跳了几次
        int jump = 0;
        int cur = 0;
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            if (cur < i){
                jump++;
                cur = next;
            }
            next = Math.max(next,i+arr[i]);
        }
        return jump;
    }

    public static void main(String[] args) {
        int[] arr={3,2,3,1,1,4};
        int i = jump(arr);
        System.out.println(i);
    }
}

贪心方法的时间复杂度为O(n)，空间复杂度为O(1)。