Jump Game 跳跃游戏

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

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

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

注意事项 这个问题有两个方法，一个是贪心和 动态规划。

贪心方法时间复杂度为O（N）。

动态规划方法的时间复杂度为为O（n^2）。

我们手动设置小型数据集，使大家阔以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。

样例 A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

ENGLISH Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Notice This problem have two method which is Greedy and Dynamic Programming.

The time complexity of Greedy method is O(n).

The time complexity of Dynamic Programming method is O(n^2).

We manually set the small data set to allow you pass the test in both ways. This is just to let you learn how to use this problem in dynamic programming ways. If you finish it in dynamic programming ways, you can try greedy method to make it accept again.

Example A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

解题思路

第i个位置是否可以到达，取决于i前面的位置的索引加上相对应位置的值是否大于或等于i。 所以为了求最后一个位置是否可以到达，可以从倒数第二个元素一次往前搜索，如果某一个元素本身可以到达，并且同时他的索引加上该位置的值大于或等于最后一个元素的索引，则可以到达。

1. 定义状态

f[i]为第i个位置是否可以到达。

2. 定义状态转移方程

if (f[i-1] && f[i-1] + A[i-1] >= i) then 
    f[i] = true;

注明 此处的i-1 应该一致检查到索引为0的位置或者其中任何一个位置使得f[i]已经可达。

3. 初始化状态

f[0] = true;

因为数组本身为非负，所以只要数组有值，第一个位置一定可达。

4. 答案

f[n - 1]

Code

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJumpDP(int[] A) {
        if (A == null || A.length == 0) {
            return false;
        }
        int n = A.length;
        boolean[] f = new boolean[n]; // default false
        f[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (f[j] && j + A[j] >= i) {
                    f[i] = true;
                    break; //already true, don't have to check further
                }
            }
        }
        return f[n - 1];
    }
}

复杂度分析

时间复杂度为：O(n^2) 空间复杂度为：O(n)

Challenge 时间复杂度O(n)

一般不推荐使用贪心算法，因为不容易证明其正确性。不过这题正好可以使用贪心算法来进行优化。 思路是遍历一次数组，存储最远能到达的地方，命名为maxDistance，如果这个值大于或等于数组长度-1，则最后一个位置可达。

那么如何更新这个maxDistance了，这个值一开始肯定和数组第一个值能到达的地方相等，所以初始值等于A[0], 然后从第数组第2个元素遍历到最后一个元素。

如果maxDistance大于当前遍历的索引值，则代表该位置可以通过前面的某个位置跳过来达到，并且同时满足这个位置的索引加上这个位置的值大于或等于maxDistance时，我们就可以把maxDistance更新为新的最远可达的位置。

贪心算法code

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        int maxDistance = 0;
        for (int i = 0; i < A.length; i++) {
            if (maxDistance >= i && i + A[i] >= maxDistance) {
                maxDistance  = i + A[i];
            }
        }
        return maxDistance >= A.length - 1;
    }

贪心优化后的复杂度

时间复杂度为：O(n) 空间复杂度为：O(1)

相关问题列表

• Jump Game I, II

Reference

Leetcode, Lintcode