Algorithm
Maximum Number of Jumps to Reach the Last Index
Solution
class Solution:
def maximumJumps(self, nums: List[int], target: int) -> int:
@cache
def dfs(i: int):
if i == len(nums) - 1:
return 0
res = -inf
for j in range(i + 1, len(nums)):
if abs(nums[i] - nums[j]) <= target:
res = max(res, dfs(j) + 1)
return res
ans = dfs(0)
return -1 if ans < 0 else ansVideo GuideLeetcode Daily
Time Complexity
O(n^2)
Space Complexity
O(n)
