暴力代码
稍微优化了一下暴力的代码,结果它过了,好神奇
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums[0] == 0 and nums.size() > 1) return false;
vector<int> f(nums.size(),0);
f[0] = 1;
for(int i = 0;i < nums.size();i++)
{
if(f[i] == 0) return false;
for(int j = 1;j <= nums[i];j++)
if(i + j < nums.size())
f[i + j]++;
else
return true;
}
return true;
}
};
动态规划
代码非常简洁,y总 yyds
class Solution {
public:
bool canJump(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); i ++ ) {
if (j < i) return false;
j = max(j, i + nums[i]);
}
return true;
}
};