[LeetCode] 55. Jump Game

Problem : https://leetcode.com/problems/jump-game/

A typical greedy algorithm problem. Iterate the input array and locate the furthest position can be reached.

Time Complexity : O ( N )

Space Complexity : O ( 1 )

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        maxSoFar = 0
        
        for i, n in enumerate(nums):
            if maxSoFar >= N - 1:
                return True
            
            if i > maxSoFar:
                return False
            
            if i + nums[i] > maxSoFar:
                maxSoFar = i + nums[i]
        
        
        return False

A memorization solution:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        
        @cache
        def helper(x):
            if x >= N-1: return True
            return any(helper(x + s) for s in reversed(range(1, nums[x] + 1)))

        return helper(0)