[Leetcode] 55. Jump Game

Solution 1

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * (n-1)
        dp += [True]

        for i in range(n-2, -1, -1):
            for j in range(i, min(n, i + nums[i] + 1)):
                if dp[j]:
                    dp[i] = True
                    break

        return dp[0]

Solution 2

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        tail = len(nums)-1
        for i in range(len(nums)-2,-1,-1):
            if(i+nums[i] >= tail):
                tail = i
        return tail == 0