程序填空题：求解袋鼠过河问题
求解袋鼠过河问题。一只袋鼠要从河这边跳到河对岸，河很宽，但河中间打了很多桩子，每隔一米就有一个，每个桩子上有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧的力量为5，就表示袋鼠下一跳最多能跳5米，如果为0，就表示会陷进去无法跳跃。河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，输出-1。
```c++
#include
#include
#define N 10001
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[N];
int dp[N];
int solve();
int main()
{ int i;
cin>>n;
for(i=0;i cin>>a[i];
int len = ;
cout< return 0;
}
int solve()
{
int i, j;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for (i = 1; i <= n; i++)
for (j = 0; j if (a[j]+j>=i)
;
return dp[n]==INF?-1:dp[n];
}
```
### 输入格式:
第一行为数组长度n，第二行依次输入n个数，用空格分隔。
```in
5
2 0111
```
### 输出格式:
输出最长跳数。
```out
4
```
答案：
第1空：solve()
第2空：dp[i]=min(dp[i],dp[j]+1)
```c++
#include
#include
#define N 10001
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[N];
int dp[N];
int solve();
int main()
{ int i;
cin>>n;
for(i=0;i
int len = ;
cout<
}
int solve()
{
int i, j;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for (i = 1; i <= n; i++)
for (j = 0; j
;
return dp[n]==INF?-1:dp[n];
}
```
### 输入格式:
第一行为数组长度n，第二行依次输入n个数，用空格分隔。
```in
5
2 0111
```
### 输出格式:
输出最长跳数。
```out
4
```
答案：
第1空：solve()
第2空：dp[i]=min(dp[i],dp[j]+1)
