#头条创作挑战赛#

题目：

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

0 <= i < j < n

-target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

示例 1：

输入：nums = [1,3,6,4,1,2], target = 2

输出：3

解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：

从下标 0 跳跃到下标 1 。从下标 1 跳跃到下标 3 。从下标 3 跳跃到下标 5 。

可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。

示例 2：

输入：nums = [1,3,6,4,1,2], target = 3

输出：5

解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：

从下标 0 跳跃到下标 1 。从下标 1 跳跃到下标 2 。从下标 2 跳跃到下标 3 。从下标 3 跳跃到下标 4 。从下标 4 跳跃到下标 5 。

可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。

示例 3：

输入：nums = [1,3,6,4,1,2], target = 0

输出：-1

解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。

提示：

2 <= nums.length == n <= 1000

-109 <= nums[i] <= 10^9

0 <= target <= 2 * 10^9

java代码：

class Solution {    // jump[i] 表示从下标 0 开始跳到 nums[i] 所需的最大跳跃次数    int[] jump;    public int maximumJumps(int[] nums, int target) {        this.jump = new int[nums.length];        Arrays.fill(jump, Integer.MIN_VALUE);        jump[0] = 0;        int maximumJumps = dfs(nums, nums.length - 1, target);        return maximumJumps >= 0 ? maximumJumps : -1;    }    // 返回从下标 i 跳到下标 0 所需最大的跳跃次数    private int dfs(int[] nums, int i, int target) {        if (jump[i] != Integer.MIN_VALUE) {            return jump[i];        }        int max = Integer.MIN_VALUE;        for (int j = i - 1; j >= 0; j--) {            int val = nums[j] - nums[i];            if (-target <= val && val <= target) {                int jump = dfs(nums, j, target) + 1;                max = Math.max(max, jump);            }        }        return jump[i] = max;    }}