/**
* 45. 跳跃游戏 II
* 给定一个非负整数数组,你最初位于数组的第一个位置。
*
* 数组中的每个元素代表你在该位置可以跳跃的最大长度。
*
* 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
*
* 假设你总是可以到达数组的最后一个位置。
*
*
*
* 示例 1:
*
* 输入: [2,3,1,1,4]
* 输出: 2
* 解释: 跳到最后一个位置的最小跳跃数是 2。
* 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
* 示例 2:
*
* 输入: [2,3,0,1,4]
* 输出: 2
*
*
* 提示:
*
* 1 <= nums.length <= 1000
* 0 <= nums[i] <= 105
*/
// 递归
class Solution {
public:
int jump(vector<int> &nums)
{
jump(nums, nums.size() - 1);
return step;
}
private:
int step{};
void jump(const vector<int> &nums, int index)
{
if (index == 0) {
return;
}
for (int i = 0; i < index; i++) {
if (i + nums[i] >= index) {
step++;
jump(nums, i);
return;
}
}
return;
}
};
// 贪心
class Solution {
public:
int jump(vector<int> &nums)
{
int step{};
int reach{};
while (reach < nums.size() - 1) {
int maxReach{};
int nextReach{};
for (int index = 1; index <= nums[reach]; index++) {
if (reach + index >= nums.size() - 1) {
return step + 1;
}
if (reach + index + nums[reach + index] > maxReach) {
nextReach = reach + index;
maxReach = nextReach + nums[nextReach];
}
}
reach = nextReach;
step++;
}
return step;
}
};
// 贪心
class Solution {
public:
int jump(vector<int> &nums)
{
int maxReach{};
int step{};
int end{};
for (int reach = 0; reach < nums.size() - 1; reach++) {
maxReach = max(maxReach, reach + nums[reach]);
if (reach == end) {
end = maxReach;
step++;
}
}
return step;
}
};