思路

假设f[N]为从i走到 i——i+a[i]的最快速度

初始化：f[1]=0,其它状态初始化为无穷大即可;

状态转移：f[i+a[i]]=min(f[i+a[i]],f[i]+1);

如果a[i]<0,跳过即可。

code

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
const int N=2010,M=200,mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef pair<ll,ll>pii;
int T;
int n;
int f[N];
int a[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    memset(f,0x3f,sizeof f);
    f[1]=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<0)continue;
        for(int j=i;j<=i+a[i];j++)
        {
            f[j]=min(f[j],f[i]+1);
        }
    }
    if(f[n]==INF)cout<<-1<<'\n';
    else cout<<f[n]<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}