LeetCode 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)返回从下标l o c locloc到下标0 00的最大跳跃次数（负数代表不可达），则dfs(n - 1)即为所求。

这个函数怎么实现呢？

• 如果loc == 0则说明达到了下标0 00，返回0 00；
• 否则，返回max ⁡ d f s ( i ) + 1 \max dfs(i)+1maxdfs(i)+1，其中0 ≤ i < l o c 0\leq i\lt loc0≤i<loc并且∣ n u m s [ i ] − n u m s [ l o c ] ∣ ≤ t a r g e t |nums[i]-nums[loc]|\leq target∣nums[i]−nums[loc]∣≤target。

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

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

AC代码

C++

/* * @LastEditTime: 2026-05-10 19:53:35 */classSolution{private:intn,target;vector<int>nums,mem;intdfs(intloc){if(loc==0){return0;}int&ans=mem[loc];// 引用if(ans){returnans;}ans=INT_MIN;for(inti=0;i<loc;i++){if(abs(nums[loc]-nums[i])<=target){ans=max(ans,dfs(i)+1);}}returnans;}public:intmaximumJumps(vector<int>&nums,inttarget){n=nums.size();this->nums=move(nums);this->target=target;mem=move(vector<int>(n));intans=dfs(n-1);returnans<0?-1:ans;}};

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

千篇源码题解已开源