Jump Game

Jump Game I

起始站在倒数第二个index的位置上，当这个index能reach到lastPos的话，就更新lastPos。最后看lastPos能不能到达0这个位置。O(n)的时间复杂度。

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

Jump Game II

解法一：DP。dp[i]代表了从头到达index i，最少需要走几步。O(n ^ 2)的复杂度。

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int[] dp = new int[nums.length];
        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[nums.length - 1] == Integer.MAX_VALUE ? -1 : dp[nums.length - 1];
    }
}

解法二：BFS，O(n)的复杂度。下一次所搜的范围是从上一次最远的起始位置+1的地方，到上一次搜索能reach到的最远的位置。

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int start = 0, end = 0, steps = 0;
        while (end < nums.length - 1) {
            steps++;
            int maxReach = end;
            for (int i = start; i <= end; i++) {
                maxReach = Math.max(maxReach, i + nums[i]);
            }
            start = end + 1;
            end = maxReach;
        }
        return steps;
    }
}