Question

2770. 达到末尾下标所需的最大跳跃次数

English Version

题目描述

给你一个下标从 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] <= 109
• 0 <= target <= 2 * 109

解法

方法一：记忆化搜索

对于每个位置 $i$，我们考虑向后搜索能跳到的位置 $j$，如果满足 $|nums[i] - nums[j]| \leq target$，那么我们就可以从 $i$ 跳到 $j$，并且从 $j$ 开始继续向后搜索。

因此，我们设计一个函数 $dfs(i)$，表示从位置 $i$ 开始跳跃到末尾下标所需的最大跳跃次数。那么答案就是 $dfs(0)$。

函数 $dfs(i)$ 的计算过程如下：

• 如果 $i = n - 1$，那么我们已经到达了末尾下标，不需要跳跃，因此返回 $0$；
• 否则，我们需要枚举从位置 $i$ 开始能跳到的位置 $j$，并计算从 $j$ 开始跳跃到末尾下标所需的最大跳跃次数，那么 $dfs(i)$ 就等于所有 $dfs(j)$ 中的最大值加 $1$。如果不存在从 $i$ 开始能跳到的位置 $j$，那么 $dfs(i) = -\infty$。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

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

class Solution {
  private Integer[] f;
  private int[] nums;
  private int n;
  private int target;

  public int maximumJumps(int[] nums, int target) {
    n = nums.length;
    this.target = target;
    this.nums = nums;
    f = new Integer[n];
    int ans = dfs(0);
    return ans < 0 ? -1 : ans;
  }

  private int dfs(int i) {
    if (i == n - 1) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int ans = -(1 << 30);
    for (int j = i + 1; j < n; ++j) {
      if (Math.abs(nums[i] - nums[j]) <= target) {
        ans = Math.max(ans, 1 + dfs(j));
      }
    }
    return f[i] = ans;
  }
}

class Solution {
public:
  int maximumJumps(vector<int>& nums, int target) {
    int n = nums.size();
    int f[n];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i == n - 1) {
        return 0;
      }
      if (f[i] != -1) {
        return f[i];
      }
      f[i] = -(1 << 30);
      for (int j = i + 1; j < n; ++j) {
        if (abs(nums[i] - nums[j]) <= target) {
          f[i] = max(f[i], 1 + dfs(j));
        }
      }
      return f[i];
    };
    int ans = dfs(0);
    return ans < 0 ? -1 : ans;
  }
};

func maximumJumps(nums []int, target int) int {
  n := len(nums)
  f := make([]int, n)
  for i := range f {
    f[i] = -1
  }
  var dfs func(int) int
  dfs = func(i int) int {
    if i == n-1 {
      return 0
    }
    if f[i] != -1 {
      return f[i]
    }
    f[i] = -(1 << 30)
    for j := i + 1; j < n; j++ {
      if abs(nums[i]-nums[j]) <= target {
        f[i] = max(f[i], 1+dfs(j))
      }
    }
    return f[i]
  }
  ans := dfs(0)
  if ans < 0 {
    return -1
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function maximumJumps(nums: number[], target: number): number {
  const n = nums.length;
  const f: number[] = Array(n).fill(-1);
  const dfs = (i: number): number => {
    if (i === n - 1) {
      return 0;
    }
    if (f[i] !== -1) {
      return f[i];
    }
    f[i] = -(1 << 30);
    for (let j = i + 1; j < n; ++j) {
      if (Math.abs(nums[i] - nums[j]) <= target) {
        f[i] = Math.max(f[i], 1 + dfs(j));
      }
    }
    return f[i];
  };
  const ans = dfs(0);
  return ans < 0 ? -1 : ans;
}