大厂面试真题详解：跳跃游戏

给出一个非负整数数组，你最初定位在数组的第一个位置。　　　
数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　　
判断你是否能到达数组的最后一个位置。

在线评测地址：领扣题库官网
样例 1

输入 : [2,3,1,1,4]
输出 : true

样例 2

输入 : [3,2,1,0,4]
输出 : false

算法：动态规划

解题思路

• 我们可以把该问题拆分成子问题，从前到后确定每个位置是否可达，用动态规划的思想求解。
• 建立dp数组，dp[i]表示能否跳到i位。

• 状态转移关系：

  • 如果存在某点j，dp[j]为true且从j可以跳到i，那么dp[i]为true
  • 否则，dp[i]为false

复杂度分析

• 时间复杂度：O(n^2)，n为数组长度。双重遍历。
• 空间复杂度：O(n)，n为数组长度。建立的dp[]长度为n。
  可行优化

• 提供一些优化的思路，大家有兴趣可以自行实现：

  1. 内层遍历改成从后向前，会比从前向后更节省时间。
  2. 仔细想想不难发现：如果可以跳到i点，则说明一定可以跳到i前面的任意一点。所以，如果i位为True，前面的位置一定是True。那么我们就无需开dp数组了，这样空间复杂度可以降到O(1)。

public class Solution {
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] A) {
        if (A.length == 0) {
            return false;
        }
        boolean[] dp = new boolean[A.length];
        dp[0] = true;
        for (int i = 1; i < A.length; i ++) {
            for (int j = 0; j < i; j ++) {
                // 如果之前的j节点可达，并且从此节点可以到跳到i
                if (dp[j] && A[j] + j >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[A.length - 1];
    }
}

更多题解参考：九章官网solution