当前位置：首页 > news >正文

跳跃游戏（二）：DFS 求解最少跳跃次数与最优路径

news 2025/9/2 12:26:18

题目描述

给定一个非负整数数组 nums，数组中每个元素代表在该位置可以跳跃的最大长度。要求找出从数组起始位置（下标 0）跳到最后一个位置（下标 nums.size() - 1）的最少跳跃次数，并输出对应的最优跳跃过程（如示例中的 0->1->4 表示从下标 0 跳到 1，再从 1 跳到 4）。

解题思路

采用深度优先搜索（DFS）的思路，从起始位置开始，尝试所有可能的跳跃步数，递归探索每一条可能的路径，同时记录跳跃次数和路径。当到达或超过最后一个位置时，更新最少跳跃次数和对应的最优路径。

核心逻辑

递归探索：从当前位置 i 出发，尝试跳跃 1 到 nums[i] 步，递归进入下一个位置 next。
路径与次数更新：每进入一个位置，将其加入当前路径；当到达终点时，若当前跳跃次数更少，则更新最少次数和最优路径。
回溯：探索完当前位置的所有可能跳跃后，将当前位置从路径中移除，回溯以探索其他可能路径。

代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;// 存储最优跳跃路径
vector<int> best_path;
// 最少跳跃次数，初始化为整型最大值
int min_jumps = INT_MAX;
// 存储跳跃数组
vector<int> nums;// 深度优先搜索函数
// i：当前位置；cnt：已跳跃次数；path：当前路径
void dfs(int i, int cnt, vector<int>& path) {// 将当前位置加入路径path.push_back(i);// 终止条件：到达或超过最后一个位置if (i >= nums.size() - 1) {// 若当前跳跃次数更少，更新最少次数和最优路径if (cnt < min_jumps) {min_jumps = cnt;best_path = path;}// 回溯，移除当前位置path.pop_back();return;}// 尝试从当前位置跳出的所有可能步数for (int j = 1; j <= nums[i]; j++) {int next = i + j;// 防止越界，直接跳到终点if (next >= nums.size()) {next = nums.size() - 1;}dfs(next, cnt + 1, path);  // 递归探索下一个位置}// 回溯，移除当前位置（所有子路径探索完后）path.pop_back();
}int main() {int n;cin >> n;nums.resize(n);for (int i = 0; i < n; i++) {cin >> nums[i];}vector<int> current_path;  // 记录当前递归路径dfs(0, 0, current_path);// 输出最少跳跃次数和最优路径cout << min_jumps << " ";for (int i = 0; i < best_path.size(); i++) {if (i > 0) {cout << "->";  // 路径中位置间用->连接}cout << best_path[i];}cout << endl;return 0;
}

代码解释

全局变量：best_path 存储最优路径，min_jumps 记录最少跳跃次数，nums 存储输入的跳跃数组。
dfs 函数：
- 每次进入函数先将当前位置 i 加入路径 path。
- 若到达终点，判断是否更新最少次数和最优路径，然后回溯。
- 遍历当前位置可跳跃的步数，递归探索下一个位置，探索完所有子路径后回溯。
main 函数：
- 读取输入的数组长度和数组元素。
- 调用 dfs 函数从起始位置 0 开始探索。
- 最后输出最少跳跃次数和最优路径。