九章算法 | 微软面试题：跳跃游戏

给出一个非负整数数组，你最初定位在数组的第一个位置。　　　

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

判断你是否能到达数组的最后一个位置。

在线评测地址：LintCode 领扣

样例 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(n2)O(n2)，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];
    }
}

更多题解参考：九章算法