🔗 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];}
};