题解 | #跳跃游戏(一)#

解题思路：

• 普通的dp会超时，在输入过程中直接执行dp，令mx_idx表示当前i下所能到达的最远下标，每次输入取所能到达下标的最大值，假如能到达下标n-1则返回true，但如果在此过程中出现下标i的v为0，而该下标恰好是mx_idx所能达到的最远下标，则不能再继续往下走，可以中断，并返回false。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int v;
    int mx_idx = 0 ;
    int dp = 1;
    for(int i = 0; i < n; ++i){
        cin>>v;
        mx_idx = max(mx_idx, i+v);
      //记录所能到达的最大下标，一旦最大下标所在位置值为0，并且不是出口下标，则不能到达。
        if(mx_idx == i && v + i == i && i != n-1) {dp = 0; break;}
    }
    dp ? cout<<"true"<<endl : cout<<"false"<<endl;
    
    return 0;
}