LC 1340 [H] Jump Game V - ALawliet/algorithms GitHub Wiki

• build a graph of all possible jumps based on the rules that it is lower and within distance
• DFS to find the longest path

more of a Medium problem

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        self.G = defaultdict(set)
        self.memo = {}

        N = len(arr)

        for i in range(N):
            for r in range(i + 1, N):
                if arr[r] < arr[i] and abs(r - i) <= d:
                    self.G[i].add(r)
                else:
                    break
            
            for l in range(i - 1, -1, -1):
                if arr[l] < arr[i] and abs(i - l) <= d:
                    self.G[i].add(l)
                else:
                    break

        res = 0

        for i in range(N):
            res = max(res, self.dfs(i, N))

        return res

    @lru_cache()
    def dfs(self, cur_idx, N):
        if cur_idx == N:
            return 0

        if cur_idx in self.memo:
            return self.memo[cur_idx]

        path = 1

        for next_hop in self.G[cur_idx]:
            path = max(path, 1 + self.dfs(next_hop, N))

        self.memo[cur_idx] = path
        return path