'''

-Medium-
*DP*
*Memoization*


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

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target
Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

 

Example 1:

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:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. 
Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. 
Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. 
 

Constraints:

2 <= nums.length == n <= 1000
-109 <= nums[i] <= 109
0 <= target <= 2 * 109



'''

from typing import List
from functools import lru_cache

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


if __name__ == "__main__":
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 2))
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 3))
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 0))
241554ce8e18b7d2d0b45402d760c9a9c3c24b64
<mask token>


class Solution:
    <mask token>


<mask token>

<mask token>


class Solution:

    def maximumJumps(self, nums: List[int], target: int) ->int:
        n = len(nums)

        @lru_cache(None)
        def dfs(i):
            if i == n - 1:
                return 0
            ret = -1
            for j in range(i + 1, n):
                if abs(nums[j] - nums[i]) <= target:
                    t = dfs(j)
                    if t >= 0:
                        ret = max(ret, 1 + t)
            return ret
        return dfs(0)


<mask token>

<mask token>


class Solution:

    def maximumJumps(self, nums: List[int], target: int) ->int:
        n = len(nums)

        @lru_cache(None)
        def dfs(i):
            if i == n - 1:
                return 0
            ret = -1
            for j in range(i + 1, n):
                if abs(nums[j] - nums[i]) <= target:
                    t = dfs(j)
                    if t >= 0:
                        ret = max(ret, 1 + t)
            return ret
        return dfs(0)


if __name__ == '__main__':
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=2))
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=3))
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=0))

<mask token>
from typing import List
from functools import lru_cache


class Solution:

    def maximumJumps(self, nums: List[int], target: int) ->int:
        n = len(nums)

        @lru_cache(None)
        def dfs(i):
            if i == n - 1:
                return 0
            ret = -1
            for j in range(i + 1, n):
                if abs(nums[j] - nums[i]) <= target:
                    t = dfs(j)
                    if t >= 0:
                        ret = max(ret, 1 + t)
            return ret
        return dfs(0)


if __name__ == '__main__':
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=2))
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=3))
    print(Solution().maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=0))

'''

-Medium-
*DP*
*Memoization*


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

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target
Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

 

Example 1:

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:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. 
Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. 
Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. 
 

Constraints:

2 <= nums.length == n <= 1000
-109 <= nums[i] <= 109
0 <= target <= 2 * 109



'''

from typing import List
from functools import lru_cache

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


if __name__ == "__main__":
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 2))
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 3))
    print(Solution().maximumJumps(nums = [1,3,6,4,1,2], target = 0))