题型:贪心算法
局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标,直接 return true 就可以了。
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size()==1) return true;
for(int i=0;i<=cover;i++){
cover = max(i+nums[i],cover);
if(cover>=nums.size()-1) return true;
}
return false;
}
};