法1:DFS（面对庞大数据时超时）
class Solution {
public:
int sign = 0, endd;
void dfs(vector<int>& nums, int step)
{
if (sign)return;//到达终点
if (step == endd)
{
sign = 1;
return;
}
for (int i = nums[step]; i >= 1; i--)
{
if(step+i<=endd)//不会越界
dfs(nums, step + i);
}
}
bool canJump(vector<int>& nums) {
endd = nums.size() - 1;
dfs(nums, 0);
if (sign)
{
return true;
}
return false;
}
};法2：贪心
如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
如果可以一直跳到最后，就成功了
class Solution {
public:
bool canJump(vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > k) return false;//i>k则到不了（最远到达的下标k<我要到的点）
k = max(k, i + nums[i]);//更新最远能到达的点的下标
}
return true;
}
};
