2770.达到末尾下标所需的最大跳跃次数：深度优先搜索(DFS)

【LetMeFly】2770.达到末尾下标所需的最大跳跃次数：深度优先搜索(DFS)

力扣题目链接：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] <= 109
• 0 <= target <= 2 * 109

解题方法：深度优先搜索

写一个函数dfs(loc)返回从下标$loc$到下标$0$的最大跳跃次数（负数代表不可达），则dfs(n - 1)即为所求。

这个函数怎么实现呢？

• 如果loc == 0则说明达到了下标$0$，返回$0$；
• 否则，返回$\max dfs(i)+1$，其中$0\leq i\lt loc$并且$|nums[i]-nums[loc]|\leq target$。

记得使用记忆化避免大量的重复计算。

• 时间复杂度$O(n^2)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-05-10 19:53:35
 */
class Solution {
private:
    int n, target;
    vector<int> nums, mem;

    int dfs(int loc) {
        if (loc == 0) {
            return 0;
        }
        int& ans = mem[loc];  // 引用
        if (ans) {
            return ans;
        }

        ans = INT_MIN;
        for (int i = 0; i < loc; i++) {
            if (abs(nums[loc] - nums[i]) <= target) {
                ans = max(ans, dfs(i) + 1);
            }
        }
        return ans;
    }
public:
    int maximumJumps(vector<int>& nums, int target) {
        n = nums.size();
        this->nums = move(nums);
        this->target = target;
        mem.assign(n, 0);
        int ans = dfs(n - 1);
        return ans < 0 ? -1 : ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源