45. Jump Game II

link

Method 1

Backtrack

class Solution:
    def jump(self, nums: List[int]) -> int:

        n = len(nums)

        @cache
        def backtrack(s):
            if s >= n - 1:
                return 0
            
            step = nums[s]


            res = float('inf')


            for i in range(s+1, s+1+step):
                res = min(res, 1 + backtrack(i))

            return res

        

        return backtrack(0)

Method 2

Greedy