1. 法一 贪心算法
为什么是贪心算法？每遍历一个数，都去考虑当前所能到达的最远下标。
class Solution {
public:
bool canJump(vector<int>& nums) {
int far=0;//最大的应该是被不断更新的
for(int i=0;i<nums.size();i++){
if(i>far) //当前所能到达的最远距离到不了i了
return false;
else
far=max(far,i+nums[i]);
}
return true;
}
};
2. 法二 贪心算法
都是贪心算法，与法一思路的不同之处在于，法一的研究对象在于nums的每一个元素，法二的研究对象在于内循环的每一组元素。
class Solution {
public:
bool canJump(vector<int>& nums) {
int count=0;
int max_dis=nums[0]; //最远下标
while(max_dis>=count){
int count_next=max_dis+1; //记录下次循环从哪个下标开始
for(int i=count;i<=max_dis;i++){
if(i>=nums.size()) break; //防止数组越界
max_dis=max(max_dis,nums[i]+i);
}
count=count_next;
}
if(max_dis>=nums.size()-1)return true;
else return false;
}
};3. 法三 动态规划
用动态规划求解更好理解
1）定义子问题：f(i):当前位置为i时，能到达的最远距离，用DP数组记录。
2）子问题的递推关系：dp[i]=max(dp[i-1],i+nums[i])
3）边界：dp[0]=nums[0]
注意：要注意的是会出现到不了下一步的情况，也就是说不是所有的dp[i]都能计算出来的（这一点和以往的动态规划不同）
?
class Solution {
public:
bool canJump(vector<int>& nums) {
int size=nums.size();
int dp[size];
dp[0]=nums[0];// 边界
for(int i=1;i<size;i++){
if(dp[i-1]<i) //如果到不了下一步!!!!!!!
return false;
else
dp[i]=max(dp[i-1],i+nums[i]); //关键代码
}
return true;
}
};
