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

从零开始的CPP(37)跳跃游戏，动态规划，贪心算法

news 来源：原创 2024/9/20 2:59:31

leetcode45

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

我最开始用递归解决

int jump(vector<int>& nums) {set<int> times;int time = 0;help(nums, 0, times, time);if (times.empty()) return 0;return *times.begin();
}
void help(vector<int>& nums, int i, set<int>& times, int& time) {if (i >= nums.size()-1) {times.insert(time);return;}else if (nums[i] == 0) {return;}for (int k = 1; k <= nums[i]; k++) {time++;help(nums, i + k, times, time);time--;}
}

时间复杂度高，无法通过。

于是使用动态规划。动态规划核心是储存。我们这里需要储存两个数值：1.当前已经达到的最远距离2.下一步能达到的最远距离

#include <vector>
using namespace std;class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();if (n <= 1) return 0; // 如果只有一个元素或为空，则不需要跳跃int maxPos = 0;       // 当前能达到的最大位置int end = 0;          // 当前步数能达到的最远位置int step = 0;         // 跳跃的步数for (int i = 0; i < n - 1; i++) { // 不需要检查最后一个位置if (maxPos >= i) {maxPos = max(maxPos, i + nums[i]); // 更新最远能跳到的位置if (i == end) {end = maxPos; // 更新当前步数能达到的最远位置step++;       // 增加一步if (end >= n - 1) break; // 如果已经达到或超过终点，则退出循环}}}return step;}
};

if (i == end) {end = maxPos; // 更新当前步数能达到的最远位置step++;

这里其实是i在追赶end（上一层是追赶maxPos），只有追赶上了，才能谈更新。

解决方案分析

为了找到最少的跳跃次数，我们需要考虑如何有效地覆盖尽可能多的索引。我们可以通过动态规划的方式来解决这个问题。这里的关键在于理解每次跳跃能够覆盖的范围，并且如何更新这个范围以达到最优解。

代码解释

初始化：
- int n = nums.size();：获取数组的大小。
- if (n <= 1) return 0;：如果数组只有一个元素或为空，则不需要跳跃，直接返回0。
定义变量：
- int maxPos = 0;：当前能达到的最大位置。
- int end = 0;：当前步数能达到的最远位置。
- int step = 0;：跳跃的步数。
遍历数组：
- 我们使用一个循环遍历数组中的每一个元素，除了最后一个元素（因为我们不需要检查最后一个元素是否能够被到达，而是要计算到达它的最少步骤）。
更新最大位置：
- 对于每个索引 i，我们更新 maxPos 为 i + nums[i] 和 maxPos 中的较大值。这是因为从当前位置 i 出发，我们最多可以跳到 i + nums[i] 的位置。
```
maxPos = max(maxPos, i + nums[i]);
```
更新步数：
- 当 i 达到了 end（即当前步数所能达到的最远位置），我们就增加了一步，并将 end 更新为新的 maxPos。
```
if (i == end) {end = maxPos;step++;
}
```
- 如果 end 已经达到或超过了终点 n - 1，则跳出循环，因为这意味着我们已经找到了最少的跳跃次数。
返回结果：
- 最后返回 step，即所需的最少跳跃次数。

贪心算法思想

贪心算法的基本思想是在每一步选择局部最优解，以期达到全局最优解。在这个问题中，我们的目标是最小化跳跃次数。为此，我们可以尝试以下策略：

在每一步，我们都会尝试覆盖尽可能多的索引，以减少总的跳跃次数。
我们将维护两个关键变量：end 和 maxPos。
- end 表示当前步数下能到达的最远位置。
- maxPos 表示从当前步数开始到下一步之间能到达的最远位置。
我们会不断地更新 maxPos，并在达到 end 时更新 end 为 maxPos，同时增加跳跃次数。