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

比眉伴天荒 2021-12-16 05:22 376阅读 0赞

【**题目**】

给定数组 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 方法：

1 public class Main {
     2     
     3     public static void main(String[] args) {
     4         int[] arr = {3,2,3,1,1,4};
     5         System.out.println(new Main().jump(arr));
     6     }
     7     
     8     public int jump(int[] arr){
     9         if(arr == null || arr.length < 2) return 0;
    10         int jump = 0; //表示跳跃步数
    11         int cur = 0; //表示跳跃 jump 步, 即当前可以到达的最远位置
    12         int next = 0; //表示多跳跃一步, 可以到达的最远位置
    13         
    14         for(int i = 0, len = arr.length; i < len; i++){
    15             if(cur < i){
        //若当前不能达到位置 i, 则需要多跳一步, 并使 cur 指向多跳一步能达到的最远位置
    16                 jump++;
    17                 cur = next;
    18                 if(cur >= len - 1){
    19                     return jump;
    20                 }
    21             }
    22             next = Math.max(next, i + arr[i]);
    23         }
    24         
    25         return jump;
    26     }
    27     
    28 }

转载于:https://www.cnblogs.com/zlxyt/p/10532506.html