Jump Game

此题DP的时间复杂度是过不了的，但是这种思维还是很基础，一个点能不能到达记做dp[i]，则dp[i]的值取决于所有小于i的位置是否能到达i这个位置，状态转移方程为

if dp[j] and nums[j] + j >= i:
    dp[i] = True
else:
    dp[i] = False

代码如下

class Solution(object):
    def canJump(self, nums):
        n = len(nums)
        dp = [False] * n
        dp[0] = True
        for i in xrange(1, n):
            for j in xrange(i):
                if dp[j] and nums[j] + j >= i:
                    dp[i] = True
                    break
        return dp[n - 1]

这道题是有贪心算法可以解的，而且思路并不算是很直观，设想我们一开始就在终点，如果真的存在一个方法跳到终点，则我们肯定是可以沿着这条路跳回去的，也就是说，如果位置i我们能到达，那就是说肯定在i之前有至少一个点位置加上可跳步数是能至少到i的，这也是DP的思想，而我们要做的就是倒回去逐个搜就行，比如i-1位置，如果这个位置能到i，我们就把需要检查的位置变为i-1再继续往回找，这样相当于我们只检查了DP里的部分中间结果，但这些结果足以让我们找到正确答案

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        last = n - 1
        for i in xrange(n - 2, -1, -1):
            if nums[i] + i >= last:
                last = i

        return last == 0

Java版本的贪心解

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int lastIndex = n - 1;

        for (int i = n - 2; i >= 0; --i) {
            if (i + nums[i] >= lastIndex) {
                lastIndex = i;
            }
        }

        return lastIndex == 0;
    }
}

Jump Game II

首先想到的是类似于青蛙跳的那道题那样的收束BFS，但是超时了

class Solution(object):
    def jump(self, nums):
        if not nums:
            return 0

        n = len(nums)
        queue = collections.deque([[0, 0]])
        checker = set([0])
        while queue:
            index, step = queue.pop()
            if index >= n - 1:
                return step
            for i in xrange(1, nums[index] + 1):
                if index + i not in checker:
                    queue.appendleft([index + i, step + 1])
                    checker.add(index + i)

        return -1

再有就是跟第一题一样的DP算法了，都是类LIS解法，代码非常简单

class Solution(object):
    def jump(self, nums):
        n = len(nums)
        dp = [sys.maxint] * n
        dp[0] = 0

        for i in xrange(1, n):
            for j in xrange(i):
                if nums[j] + j >= i:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[n - 1]

此题的贪心算法，就很有点BFS和双指针混合的意思了，因为我们必然是从起点开始跳，那这样我们利用双指针维护一个变长窗口，一开始这个窗口只有一个数就是起点的元素，我们利用对这个窗口里面的数进行遍历，找到在这个窗口里面跳一步能到达的最远位置，而下一个活动窗口就变成了当前窗口的右边界位置加一到这个最远位置了，这样相当于我们对每个元素只检查了一次，没有额外操作了，而一直推进这个变长窗口直到它覆盖终点为止，它覆盖终点时的窗口数其实就是最后的答案了，这里每次推进窗口的思路和BFS基本一致，而双循环O(n)时间复杂度，指针边界变换这些又是明显的双指针特征

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return 0

        start, end = 0, n - 1
        curLeft, curRight = 0, 0
        nextRight = 0
        count = 0
        while start <= end:
            count += 1
            for i in xrange(curLeft, curRight + 1):
                if nums[i] + i >= end:
                    return count
                nextRight = max(nums[i] + i, nextRight)

            curLeft = curRight + 1
            curRight = nextRight
        return -1