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

dp, https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/

给你一个下标从 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

这是一个典型的动态规划问题。我们需要从下标 $0$ 跳到下标 $n - 1$ ，并且每次跳跃必须满足步长限制（值之差的绝对值不超过 target）。由于我们要找的是最大跳跃次数，且跳跃方向固定（从小下标到大下标），可以通过动态规划来解决。

解题思路

定义状态：令 dp[i] 表示到达下标 i 所需的最大跳跃次数。
状态初始化：
- 初始化 dp 数组，长度为 n。
- dp[0] = 0（起始位置跳跃次数为 0）。
- 其他位置初始化为一个特殊值（例如 -1 或负无穷），表示该位置暂时不可达。
状态转移方程：对于每一个位置 j（从 $1$ 到 $n - 1$ ），我们遍历它之前的所有位置 i（从 $0$ 到 $j - 1$ ）：
- 如果满足条件 abs(nums[j] - nums[i]) <= target；
- 并且位置 i 是可达的（即 dp[i] != -1）；
- 那么我们可以从 i 跳到 j，此时 dp[j] = max(dp[j], dp[i] + 1)。
返回结果：最后返回 dp[n-1]。如果 dp[n-1] 仍然是 -1，说明无法到达终点。

代码实现

python

from typing import List

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        # dp[i] 表示到达下标 i 的最大跳跃次数
        # 初始化为 -1 表示当前下标不可达
        dp = [-1] * n
        dp[0] = 0
        
        # 遍历每一个目标位置 j
        for j in range(1, n):
            # 遍历之前的所有可能跳出的位置 i
            for i in range(j):
                # 检查是否满足跳跃条件：
                # 1. 前驱节点 i 必须是可达的 (dp[i] != -1)
                # 2. 两个下标对应的值之差的绝对值不超过 target
                if dp[i] != -1 and abs(nums[j] - nums[i]) <= target:
                    dp[j] = max(dp[j], dp[i] + 1)
        
        return dp[n - 1]

复杂度分析

时间复杂度： $O (n^{2})$ 。其中 $n$ 是数组 nums 的长度。我们需要两层嵌套循环：外层循环运行 $n$ 次，内层循环运行次数从 $1$ 增加到 $n - 1$ 。总计算次数约为 $n^{2} / 2$ 。由于题目给定 $n \leq 1000$ ， $n^{2} = 1, 000, 000$ ，在 Python 的执行时限内完全没问题。
空间复杂度： $O (n)$ 。需要一个长度为 $n$ 的 dp 数组来存储中间状态。

示例解析（以示例 1 为例）

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

dp[0] = 0
j=1 (nums[1]=3): i=0 满足 |3-1|<=2 -> dp[1] = 1
j=2 (nums[2]=6): i=0,1 均不满足条件 -> dp[2] = -1
j=3 (nums[3]=4): i=1 满足 |4-3|<=2 -> dp[3] = dp[1]+1 = 2
j=4 (nums[4]=1): i=0 满足 |1-1|<=2 -> dp[4] = dp[0]+1 = 1
j=5 (nums[5]=2):
- i=1 满足 -> dp[5] = max(-1, 1+1) = 2
- i=3 满足 -> dp[5] = max(2, 2+1) = 3
- i=4 满足 -> dp[5] = max(3, 1+1) = 3 最终结果：3

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

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