问题 1277 --简单跳跃

1277: 简单跳跃

时间限制: 1 Sec  内存限制: 128 MB
提交: 468  解决: 182
[提交][状态][讨论版][命题人:]

题目描述

有n个格子排成一排，一枚棋子，最初在第一个格子上(最左边的格子为第一个格子)，每个格子上有一个数字a，表示在该格子上一步最多可以往后跳a格，现给出n个格子及每个格子上的数字，求出从第一个格子跳到最后一个格子所需最小步数。

如图所示：

共五个格子，其各个值为2,3,1,1,4，棋子可以从第一个格子跳到第二个格子，再从第二个格子跳到第五个格子，即可走2步到最后一个格子。

输入

第一行一整数n
随后一行n个整数ai，表示格子从左到右每个格子上的数值
2<=n<=1000
0<=ai<=109

输出

一行一个整数表示最小步数，如果不能跳到最后一个格子，输出-1

样例输入

5
2 3 1 1 4

样例输出

2

提示

来源

贪心 线性dp、dfs、bfs 

[提交][状态]