题目分析
动态规划:
由题意不难得出 f[i]=((a[i-1]+i-1>=i)&&f[i-1] || (a[i-2]+i-2>=i)&&f[i-2] || ……)
再考虑如何化简式子:
看 a[i-k]+i-k>=i
,即 a[i-k]>=k
,令 i-k=t
,则 a[t]>=i-t
,即 a[t]+t>=i
则将上式化为f[i]=((a[1]+1>=i)&&f[1] || (a[2]+2>=i)&&f[2] || ……)
所以预处理出a[i]+i,令maxs=-1,从1到n扫,如果 f[i]==true
,就用a[i]+i更新maxs即可
class Solution {
public:
bool f[100010];
bool canJump(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++)nums[i]+=i;
int maxs=-1;
for(int i=0;i<n;i++)
{
if(i==0)f[i]=true,maxs=max(maxs,nums[i]);
else
{
if(maxs>=i)f[i]=true;
if(f[i]==1)maxs=max(maxs,nums[i]);
}
}
return f[n-1];
}
};