[LintCode] 116 Jump Game 解题报告

Description
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.


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


思路
动态规划
初始值f[0]设置为true，表示可达。遍历左右点。当前点是否可达取决于之前所有点中可达的点加上他们能跳到的地方。时间复杂度O(n²)，空间复杂度O(n)。

贪心法
维护一个能达到的最远的值。每经过一个点，比较一下这个点可以到的值和这个最远值，并更新。最后判断最远值是不是超过了最后一个index。时间复杂度O(n)，空间复杂度O(1)。


Code
动态规划

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        // wirte your code here
        boolean jumpStatus[] = new boolean[A.length];
        jumpStatus[0] = true;
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (jumpStatus[j] == true && j + A[j] >= i) {
                    jumpStatus[i] = true;
                    break;
                }
            }
        }
        return jumpStatus[A.length - 1];
    }
}

贪心

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        // wirte your code here
        int maxReach = 0;
        for (int i = 0; i < A.length; i++) {
            if (i <= farthest) {
                maxReach = Math.max(maxReach, i + A[i]);
            }
            if (maxReach >= A.length - 1) {
                return true;
            }
        }
        return false;
    }
}