Jump Game

55. Jump Game

Niave DFS + memo got TLE

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        from functools import lru_cache
        @lru_cache(None)
        def dfs(i):
            if i+nums[i]>=len(nums)-1:return True
            if i!=len(nums)-1 and nums[i]==0:return False
            return any(dfs(i+d) for d in range(1, nums[i]+1))
        return dfs(0)

1 pass DP got AC

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        for i, num in enumerate(nums):
            if i>max_reach:return False
            max_reach = max(max_reach, i+num)
        return True