【算法】【递归与动态规划模块】跳跃游戏

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定数组arr，arr[i] 为k ，代表当前位置能够往前面跳跃1~k个单位，求到达arr尾部的最少步数。
如：
[3,2,3,1,1,4]
最少步数：从arr[0] 跳跃到arr[2]从arr[2]跳跃到中点一共两步。结果为2

解决方案

原问题：
递归方法：
常规递归方法即可解答，定义递归函数f(arr, i) 表示从arr[i]出发到达arr终点的最少步数.
每一个状态遍历即可。
动态规划方法：
将常规递归方法转成动态规划即可，构建一维数组dp，dp[i]表示从arr[i] 到达终点所需最少步数.
最优解：
设计三个变量jump、cur、next。jump表示 到达当前位置已经跳了多少步了，cur表示当前位置只能跳一步的话能跳的最远距离、next表示当前位置跳两步的话最远能够跳多远。
对于每一个arr[i] 计算cur是否能够到达i，如果能到达，则不需要增加步数，查看到达的地方是否能够更新next。如果不能到达，则需要增加步数，cur变成next，next持续更新。详情见代码，原理见思考。

代码编写

java语言版本

原问题：
经典递归版本：

     /**
     * 二轮测试：递归方法
     * @return
     */
    public static int jumpCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return processCp1(arr, 0);
    }

    private static int processCp1(int[] arr, int i) {
        // -1表示跳不过去
        int res = Integer.MAX_VALUE;
        if (i >= arr.length) {
            // 超出去了，无法达到，直接返回最大值
            return Integer.MAX_VALUE;
        }
        if (i == arr.length-1) {
            // 已经到了,返回0步即可
            return 0;
        }
        int step = arr[i];
        for (int j = 1; j <= step; j++) {
            res = Math.min(res, processCp1(arr, i+j));
        }
        return res == Integer.MAX_VALUE ? -1 : res + 1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

经典动态规划版本：

    /**
     * 二轮测试：动态规划
     * @return
     */
    public static int dpCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        dp[arr.length-1] = 0;
        for (int i = arr.length-2; i >= 0; i--) {
            int step = arr[i];
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= step; j++) {
                min = Math.min(min, dp[i+j]);
            }
            dp[i] = min + 1;
        }
        return dp[0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最优解：

    /**
     * 最优解
     * 时间 o（n) 空间 O(1)
     * @param arr
     * @return
     */
    public static int superCp1(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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题是一道单路线型的递归，并且很容易想到，这里就不解释了，主要思考一下最优解的优化点在什么地方
首先最优解的空间复杂度O(1),时间O(N), 递归和动态规划都没有达到这个复杂度。

首先有一个重要的指标就是，当cur小于i的时候需要跳跃了，这个时候跳跃数+1，cur=next，这里next已经遍历出了cur到i之间每一个位置能够到达的最远距离，所以这里cur跳到的位置就是能够跳到最远距离的那个位置，但是我们不关心，我们只关心下一跳能够跳到的最远距离，所以i只会递增，此时cur和i之间的位置不需要再遍历了，因为cur和i之间的距离没有一个能够跳的不cur更远的，但是递归就会暴力的尝试每一种情况导致了时间复杂度增加了一个维度。
这两种解法之间的不同在于角度，递归关心的是步数，而最优解将眼光投到了每一步中能够跳的最远位置。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！