055._jump_game.md

###55. Jump Game

题目: https://leetcode.com/problems/jump-game/

难度:

Medium

dp

问题出现在一旦有0，而且这个0是不可跨过的那么无解，无法达到 貌似对于dp[i] <= i，就无法达到，不能成立

尝试一：

超时

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 2: return True

        far = [0 for i in range(len(nums))]
        far[0] = nums[0]

        for i in range(len(nums)-1):
        	for j in range(i):
        		if far[j] > far[i]:
        			far[i] = far[j]
        	far[i] = max(far[i],i+nums[i])
        	if far[i] <= i:
        		return False
        return True

尝试二，看了hint，根本不用这个数组，直接用一个数来记录可达最远距离，非常巧妙

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        i = 0
        reach = 0

        # i > reach also means terminate it can not really reach 
        while i < len(nums) and i <= reach:
        	reach = max(i+nums[i],reach)
        	i += 1

        return reach >= len(nums) -1

i记录当前loop位置，reach记录当前可到位置

注意这里的while循环的条件是 i < len(nums) and i <= reach，之所以加上 i <= reach 是因为如果reach < i说明i层不可达，其实也可以直接terminate.也就是我一开始写的dp[i] <= i会导致依旧不可达。