[数据结构与算法]LeetCode-55. 跳跃游戏

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

分析阶段

动态规划

输入一个数组 $nums$，可以从下标 $i$ 处，最远跳到下标 $i+nums[i]$ 处，判断是否能从下标0开始，跳跃到数组的最后一个下标。

按照“动态规划”的解题思路，我们需要确定：状态、base case、数组、状态转移方程。

1、问题类型

第二类：对某种数结构和算法的使用

使用的算法：动态规划

数据结构：构造状态数组

2、解题思路

解法1

$nums[i]$ 记录的是在下标 $i$ 处能够跳跃的最远距离，如果 $nums[i]=j$，那么在下标 $i$ 处就能跳跃到范围 $i,i+1,i+2,...,i+j$ 中的任意一个下标处。因此，只要下标0处能够跳跃的最远距离大于等于 $n?1$，就能从起点跳跃到最后一个下标。

我们通过计算每个下标处能够跳跃的最远距离，来求解最终结果。求解过程如下：

1、要求解的“状态”是：输入长度为 $n$ 的数组，要判断是否能够跳跃到最后一个下标；

2、简化状态，得到“base case”：在最后一个下标处，能够跳跃的最远下标是$n?1$；

3、构造“数组”：构造一个长度为 $n$ 的数组 $dp$，$dp[i]$ 的值表示在下标 $i$ 处，最远能够跳跃到的最远下标；

4、构造状态转移方程：

在下标 $i$ 处，它的值为 $nums[i]=j$，意味着可以跳跃到 $i,i+1,i+2,...,i+j$ 中的任意一个下标处，并继续向后跳跃，直到某个下标值为0。因此 $dp[i]$ 的值时 $dp[i+1],...,dp[i+j]$ 中的最大值。

状态转移方程如下：
$$dp[i]=?\begin{array}{ll}n?1,& i==n?1\\ max(dp[i+1],...,dp[i+j]),& nums[i]==j,i<n?1\end{array}$$
代码实现在“编码阶段-实现1”部分。

从代码中可以看出，每个下标处都要在一个范围内找出最大值，性能很差，在 LeetCode 的提交结果如下：

解法2

问题要求解的是”能否跳到最后一个下标“，所以我们可以直接判断在一个下标处是否能够跳跃到最后一个下标。求解过程如下：

1、要求解的“状态”是：输入长度为 $n$ 的数组，要判断是否能够跳跃到最后一个下标；

2、简化状态，得到“base case”：输入的数组长度为1，一定可以到达；

3、构造“数组”：构造一个长度为 $n$ 的数组 $dp$，$dp[i]==true$ 表示能够跳到下标 $i$；

4、构造状态转移方程：

（1）因为从数组的下标0开始起跳，所以如果数组长度 $n==1$，一定可以跳到；

（2）如果 $n>1$，且 $nums[0]==0$，不能从起点继续向后跳跃，此时 $dp[i]=false$；

（3）如果可以跳跃到下标 $i$，假设 $nums[i]==j$，那么此时可以跳跃的范围下标是：$[i+1,i+2,...,i+j]$，更新 $dp[i+1,i+2,...,i+j]=true$。

状态转移方程如下：
$$dp[i]=?\begin{array}{ll}true,& n==1\\ false,& nums[0]==0,n>1\\ true,& ?k<i,k+nums[k]\ge i\end{array}$$
代码实现在“编码阶段-实现2”部分。

在代码中，从0开始向后遍历，为了避免重复设置 $dp $中的值，使用变量 $maxIndex$ 表示已知可以跳跃到的最远下标，后面的遍历可以从 $maxIndex$ 开始设置值。在 LeetCode 上的结果如下：

解法3

第三种解法来自官方题解，它最关键的思想就是：如果可以跳跃到下标 $i$，并且 $i+nums[i]\ge n?1$，那么就一定能跳跃到最后一个下标。

所以，我们要做的就是：从0开始向后遍历，不断更新能够跳跃到的最远下标，在这个下标范围内找到能够跳跃到最后一个下标的位置。

代码实现在“编码阶段-实现3”部分。

编码阶段

实现1

public boolean canJump(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        dp[i] = getMax(dp, i + 1, i + nums[i]);
    }
    return dp[0] >= n - 1;
}

/**
 * 从数组 dp 中，取出 dp[start,...,end] 范围内的最大值
 */
private int getMax(int[] dp, int start, int end) {
    int max = -1;
    for (int i = start; i <= end; i++) {
        if (i >= dp.length) {
            return max;
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}

实现2

public boolean canJump(int[] nums) {
    // 
    if (nums.length == 1) {
        return true;
    } else if (nums[0] == 0) {
        return false;
    }

    boolean[] dp = new boolean[nums.length];
    dp[0] = true;
    dp[1] = true;
    // 用来避免重复设置
    int maxIndex = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        // 如果不能到达，跳过
        if (!dp[i]) {
            continue;
        }
        // [j,j+1,j+2,...,j+num[i]] 范围内的下标都可以跳跃到
        // 通过 maxIndex 避免重复设置
        for (int j = maxIndex; j <= nums[i] + i; j++) {
            maxIndex = j;
            if (j < nums.length && !dp[j]) {
                dp[j] = true;
            }
        }
    }
    return dp[nums.length - 1];
}

实现3

public boolean canJump(int[] nums) {
    // 当前能够跳跃的最远下标
    int max = nums[0];
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        // i <= max，表示能够达到下标 i 处
        if (i <= max) {
            // 更新 max 值
            max = Math.max(max, nums[i] + i);
            // 如果 max >= n-1，说明从当前位置能够跳跃到最后
            if (max >= n - 1) {
                return true;
            }
        }
    }
    return false;
}

总结阶段

“跳跃游戏“关键是找到它的核心思路：

1、能够跳到当前位置

2、当前位置能够跳到的最远下标

只要维护“当前能够跳跃到的最远下标”，就能只需要一次遍历得到结果。