Maximum Number of Jumps to Reach the Last Index — LeetCode 2770 Python Solution

The problem

You are given a 0-indexed array nums of n integers and an integer target. You are initially positioned at index 0.

Example

Input

nums = [1,3,6,4,1,2], target = 2

Output

3

Explanation

To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:

Python solution

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n - 1:
                return 0
            ans = -inf
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) <= target:
                    ans = max(ans, 1 + dfs(j))
            return ans

        n = len(nums)
        ans = dfs(0)
        return -1 if ans < 0 else ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2770. Maximum Number of Jumps to Reach the Last Index is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems