2770. Maximum Number of Jumps to Reach the Last Index

link

First version

# need prune otherwise tle
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        
        n = len(nums)
        
        self.res = -1
        self.M = defaultdict(int)
        
        @cache
        def backtrack(s, current):
            
            # prune
            if self.M[s] and self.M[s] >= current:
                return
            
            self.M[s] = current
            
            if s == n - 1:
                self.res = max(self.res, current)
                return
            
            seen = set()
            
            for i in range(s+1, n):
                # prune
                if nums[i] not in seen and abs(nums[i] - nums[s]) <= target:
                    seen.add(nums[i])
                    backtrack(i, current + 1)

        
        
        
        backtrack(0, 0)
        
        
        
        return self.res

Only use one params

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

        n = len(nums)

        @cache
        def backtrack(s):
            if s == 0:
                return 0

            res = - 1
            
            for i in range(s-1, -1, -1):
                if abs(nums[s] - nums[i]) > target:
                    continue
                cur = backtrack(i)
                if cur != -1:
                    res = max(res, 1 + cur)
                

            return res

        
        r = backtrack(n-1)


        return -1 if r == 0 else r