递归和动态规划问题：跳跃游戏

【题目】

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

【举例】

　　arr=[3, 2, 3, 1, 1, 4]。

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

【要求】

　　如果 arr 的长度为 N， 要求实现时间复杂度为 O(N), 额外空间复杂度为 O(1)。

【难度】

　　一星

【解答】

1. 整型变量 jump, 代表目前走了多少步，初始值为 1；整型变量 cur, 代表在能走 jump 步的情况下，可以到达的最远位置，初始值为 arr[0]；整型变量 next, 代表如果多走一步，可以达到的最远位置，初始值为 arr[0]。
2. 从左到右遍历 arr, 假设遍历到位置 i:

• 如果 cur >= i, 说明跳 jump 步可以到达位置 i, 此时什么都不做。当 cur >= arr.length-1 时， 可直接返回 jump.
• 如果 cur < i, 说明跳 jump 步不可以达到位置 i, 此时要先多跳一步，令 jump++, cur = next. 

　　  3. next 代表着位置 i 前面的位置多跳一步可以到达的最远位置， i + arr[i] 代表着从位置 i 多跳一步可以到达的位置，两者之间的最大值  Math.max(next, i+arr[i]) 即为达到位置 i 或 位置 i 之前的位置多跳一步可以达到的最远位置, 赋值给 next.

　　具体代码实现请参考如下代码中的 jump 方法：

public class Main {
    
    public static void main(String[] args) {
        int[] arr = {3,2,3,1,1,4};
        System.out.println(new Main().jump(arr));
    }
    
    public int jump(int[] arr){
        if(arr == null || arr.length < 2) return 0;
        int jump = 0; //表示跳跃步数
        int cur = 0; //表示跳跃 jump 步, 即当前可以到达的最远位置
        int next = 0; //表示多跳跃一步, 可以到达的最远位置
        
        for(int i = 0, len = arr.length; i < len; i++){
            if(cur < i){//若当前不能达到位置 i, 则需要多跳一步, 并使 cur 指向多跳一步能达到的最远位置
                jump++;
                cur = next;
                if(cur >= len - 1){
                    return jump;
                }
            }
            next = Math.max(next, i + arr[i]);
        }
        
        return jump;
    }
    
}