动态规划之跳跃游戏详解

跳跃游戏的动态规划求解过程花了我很多时间才看明白，在这里会写的很详细分享给大家。

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

举例：arr=[3,2,3,1,1,4,2]，arr[0]=3，选择跳到位置2；arr[2]=3，可以跳到位置5；arr[5]=4，选择跳到位置6即最后的位置。这是最少的跳法，所以返回3。

要求：若arr长度为N，实现一种时间复杂度为O(N),空间复杂度为O(1)的方法。

最直接的解法是暴力递归，但是时间复杂度是指数级，可以选择动态规划的方法来求解。

如下图所示，以arr=[3,2,3,1,1,4,2]为例。jump[i]代表跳到当前位置i的最少次数，可以看出jump[6]就是我们要求解的。求jump[6]之前我们定义另外一个变量，cur[i]代表跳jump[i]次能到达的最远位置，next是解决问题最关键的一个变量，先忽略掉，稍后会详细讲解。

jump[i]是可以用jump[i-1]和cur[i-1]表示出来的，如下式所示。

这个公式什么意思呢？如下图，假设位置2之前的变量都已知了，如何求jump[3]，很简单，因为到位置2只需要jump[2]=1步，而1步最远能到位置3(cur[2])，换句话说到达位置3只需要1步，即jump[3]=jump[2]，当cur[3-1]>=3。同理求jump[4]，到达位置3只需要jump[3]=1步，而1步最远能到位置3(cur[3])，显然要到位置4至少要3+1=4步，即jump[4]=jump[3]+1，当cur[4-1]<4。那么我们只要知道所有的cur就能按照这个公式一次递推到jump[6]。另外，可以看出，cur[i-1]>=i这个条件的意义就是判断是否需要比前一个位置多跳一次。

那么cur怎么求解呢？也有一个公式:

这个公式又是怎么来的呢？首先得清楚cur[i]表示的什么，它表示是到达位置i至少需要跳jump[i]次然后跳jump[i]次能到的最远位置。如下图，到位置2需要跳jump[2]=1次，而跳1次能到的最远位置是位置3(cur[2])，也就是到位置3的最少步数还是1次，所以cur[3]=cur[2]。同理，到达位置3需要跳jump[3]=1次，而跳1次能到的最远位置是位置3(cur[2])，也就是到位置4的最少步数需要2次，2次能达到的最远距离是多少呢？只有cur是无法求出的，因为目前我们的cur[0:3]只能让我们知道跳0次和跳1次能到达的最远位置，这个时候就要借助next变量了。

给出一个next的表达式：，容易看出arr[j]+j表示的是在位置j上再跳一步能到达的最远位置

下面说明next[i-1]在cur[i-1]<i的时候表示（或者说等于）跳jump[i]次能到达的最远位置，即next[i-1]=cur[i]，而在其他情况下不一定相等。

如下图，假设要知道跳3次最远能达到的位置cur[6]，我们可以找出第2次可能跳到的所有位置j，然后比较所有arr[j]+j中的最大值即可。当然也可以找出所有小于三次跳到的位置的j+arr[j]再比较出最大值，因为跳0次和跳1次到的位置情况下j+arr[j]是小于等于跳2次的j+arr[j]，不会改变这个最大值。所以，我们求的cur[i]等于跳小于jump[i]次能到的所有位置的j+arr[j]的最大值，next[i-1]的表达式的意义是所有位置i之前的j+arr[j]的最大值，当cur[i-1]<i时位置i之前的jump[j]都小于jump[i]，位置i及之后的jump[j]都大于等于jump[i]，所以此时next[i-1]=cur[i]。

如下图所示,显然不满足cur[i-1]<i条件时next[i-1]不一定等于cur[i],如next[3-1]!=cur[3]。原因是此时求小于jump[3]的j+arr[j]的最大值是不包括位置1和2的j+arr[j]的，但是next表达式给出的定义是位置i之前的j+arr[j]的最大值，把位置1和2的包括进去了。

最后根据下面三个递推公式可求解这个动态规划问题，填表过程如下图所示。

虽然此时时间复杂度为O(N),但空间复杂度也是O(N),因为我们需要分配三个长度也为N的数组给jump，cur，next。不过这可以优化，从上图的填表过程我们发现jump，cur，next在位置i上的值只依赖位置i-1上的值，因此不用分配数组，只需覆盖更新即可。

最后java实现代码如下：

public 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;
}