牛客网 搜狐2017秋招研发工程师笔试试卷（二）- 袋鼠过河

链接：https://www.nowcoder.com/questionTerminal/74acf832651e45bd9e059c59bc6e1cbf?toCommentId=1118302
来源：牛客网

• 空间限制：32768K

一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1

输入描述:

输入分两行，第一行是数组长度N (1 ≤ N ≤ 10000)，第二行是每一项的值，用空格分隔。

输出描述:

输出最少的跳数，无法到达输出-1

示例1

输入

5
2 0 1 1 1

输出

4

分析：

校赛时有这个题，当时看出是dp题，感觉私立也对，但是就是提交不过，然后下来看到别人的思路我明白了，是我把问题想得太复杂了，更本不用分的那么详细。

在本题中，再次加深了一个函数的运用，memset，memset函数按字节对内存块进行初始化，所以不能用他将int数组初始化为0和-1之外的其他值了，总是的不到正确的答案，然后改了一下这里就过了。

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;

const int N=10005;
#define INF 99999999
int dp[N],s[N];

int main()
{
    int n;
    for(int i=0;i<N;i++)///初始化dp数组
        dp[i]=INF;
    dp[0]=0;///记住这里的以一个要设置为0
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)///然后来更新大dp[i]的值
    {
        for(int j=0;j<i;j++)
        {
            if(j+s[j]>=i)///如果从j位置能到达i位置，就看看能否更新dp[i]的数组
                dp[i]=min(dp[i],dp[j]+1);
        }
    }
    printf("%d\n",dp[n]==INF?-1:dp[n]);
    return 0;
}