力扣 45. 跳跃游戏 II
🔗 https://leetcode.cn/problems/jump-game-ii
题目
- 给一个数组 nums，最开始在 index 0，每次可以跳跃的区间是 0-nums[i]
- 保证可以跳到 nums 的末尾，返回跳到末尾的最小步骤
思路
- 题解是贪心，选择每次可以跳到的最远位置
- 代码是模拟，每次更新从当前位置可以跳到的位置的最小步数，性能不佳，可 AC
代码
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> vec(n);
for (int i = 0; i < nums.size() -1; i++) {
if (nums[i] == 0) continue;
int m = min(n-1, i + nums[i]);
for (int j = i + 1; j <= m; j++) {
if (vec[j] == 0) vec[j] = vec[i] + 1;
else vec[j] = min(vec[j], vec[i] + 1);
}
}
return vec[n-1];
}
};