思路
我写的好像是动规的做法。
设 \(f_{i,j}\) 表示第 \(i\) 步 \(j\) 个点是否可以走到，值要么为 \(1\)，要么为 \(0\)。最多走 \(n\) 步，因为总共只有 \(n\) 个点，每一步都肯定会多延伸出一个点，要不然就重复计算。
不难得出转移公式：
\(f_{i+1,j+k_j}=f_{i,j}\)
\(f_{i+1,j-k_j}= f_{i,j}\)
解释一下，因为只能从后往前，不然如果从当前往上一步就有需要一层循环。
注意：
- 第一个转移执行前提是 \(j+k_j \le n\)。
- 第二个转移执行前提是 $1 \le j- k_j $，如果不判断就会数组越界。
AC CODE
#include<bits/stdc++.h>
using namespace std;
int f[205][205],n,a,b,k[205];
int main(){
cin>>n>>a>>b;
for(int i=1;i<=n;i++)cin>>k[i];
f[0][a]=1;
for(int i=0;i<n;i++){
for(int j=1;j<=n;j++){
if(f[i][j]==0)continue;
if(j+k[j]<=n){f[i+1][j+k[j]]=f[i][j];}
if(j-k[j]>=1)f[i+1][j-k[j]]=f[i][j];
}
}
for(int i=0;i<=n;i++){
if(f[i][b]){
cout<<i;
return 0;
}
}
cout<<-1;
return 0;
}