文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Jump Game
2. Solution
- 递归遍历所有的可能
class Solution {
public:
bool canJump(vector<int>& nums) {
return jump(nums, 0);
}
bool jump(vector<int>& nums, int start) {
if(start + nums[start] >= nums.size() - 1) {
return true;
}
for(int i = 1; i <= nums[start]; i++) {
if(nums[start + i] != 0) {
if(jump(nums, start + i)) {
return true;
}
else {
nums[start + i] = 0;
}
}
}
nums[start] = 0;
return false;
}
};
- 贪心算法
class Solution {
public:
bool canJump(vector<int>& nums) {
int current = nums.size() - 1;
for(int i = current - 1; i >= 0; i--) {
if(nums[i] + i >= current) {
current = i;
}
}
if(current == 0) {
return true;
}
else {
return false;
}
}
};
