描述
寒假在家里无聊极了，小w看到地上的瓷砖，想出了一个游戏。这个游戏是这样子的，一共有n个格子，刚开始在起点的时候可以跳到第1个到第k个格子中的一个上面，之后在每个格子上只能向前跳相对应的长度。请问至少需要多少步可以恰好跳到最后一个格子呢？
输入
第一行输入两个整数n和k(1<=n<=100000,1<=k<=n)。
第二行输入n个整数，第i个整数代表在第i个格子上能跳跃的长度（0<=a[i]<=100000)。
输出
输出能跳到第n个格子的最少步数。如果无法到达，输出-1。
样例输入
7 3
4 2 5 1 2 1 1
样例输出
3
提示
在起点跳到第1个位置，1->5->7
在起点跳到第2个位置，2->4->5->7
在起点跳到第3个位置：3->8
这题太牛逼了，简直是深搜、广搜、动态规划教学题
动态规划解法
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10,inf = 0x3f3f3f3f; int n,k; int a[N],f[N]; int main() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; memset(f,inf,sizeof(f)); for(int i=1;i<=k;i++)f[i] = 1; for(int i=1;i<=n;i++) { int x = a[i]+i; if(x<=n) { f[x] = min(f[x],f[i]+1); } } if(f[n]==inf)cout<<"-1"; else cout<<f[n]; return 0; }