【LetMeFly】2770.达到末尾下标所需的最大跳跃次数深度优先搜索(DFS)力扣题目链接https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/给你一个下标从0开始、由n个整数组成的数组nums和一个整数target。你的初始位置在下标0。在一步操作中你可以从下标i跳跃到任意满足下述条件的下标j0 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] 1090 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≤iloc并且∣ 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;vectorintnums,mem;intdfs(intloc){if(loc0){return0;}intansmem[loc];// 引用if(ans){returnans;}ansINT_MIN;for(inti0;iloc;i){if(abs(nums[loc]-nums[i])target){ansmax(ans,dfs(i)1);}}returnans;}public:intmaximumJumps(vectorintnums,inttarget){nnums.size();this-numsmove(nums);this-targettarget;memmove(vectorint(n));intansdfs(n-1);returnans0?-1:ans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源