DP28 跳跃游戏(三)

题解：1.先判断是否可以到达最后一个值，如果不能到达直接返回-1；

2.如果可以到达最后一个位置，用dp求到达最后一个位置所需的最小次数，dp[i]表示到达第i个位置所需的最小次数，具体dp详情，见代码。

描述

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。

1.如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0)，请返回-1

2.数据保证返回的结果不会超过整形范围，即不会超过2^{31}-1231−1

数据范围:

0<=nums.length<=10^50<=nums.length<=105

0<=nums[i]<=10000<=nums[i]<=1000

输入描述：

第一行输入一个正整数 n 表示数组 nums的长度

第二行输入 n 个整数，表示数组 nums 的内容

输出描述：

输出最少跳几次到最后一个位置

示例1

输入：

7
2 1 3 3 0 0 100

复制输出：

3

复制说明：

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，step=1

 再跳到nums[3]=3的位置，step=2

再直接跳到nums[6]=100，可以跳到最后，step=3，返回3

示例2

输入：

7
2 1 3 2 0 0 100

复制输出：

-1

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int num[100005];
int dp[101005];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
     if(n==0)
    {
        printf("-1\n");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
    }
    int idx=0;
    idx=num[1]+1;
    int t=0;
    for(int i=2;i<=n;i++)
    {
        if(idx>=i)
        {
            int m=i+num[i];
            if(m>idx)
            {
                idx=m;
            }
        }
        else{
            t=1;
            break;
        }
    }
    if(t || idx<n)
    {
        printf("-1\n");
    }
    else{
        int id=0;
        for(int i=1;i<=n;i++)
        {
            if(i==1) 
                {
                id=i+num[i];
                dp[i]=0;
            }
            
            else{
                if(id>=i)
                {
                    int m=i+num[i];
                    if(m>id)
                    {
                        id=m;
                    }
 
                }
            }
             for(int j=1;j<=num[i];j++)
             {
                 if(dp[i+j]!=-1)
                 {
                     dp[i+j]=min(dp[i+j],dp[i]+1);
                 }
                 else{
                     dp[i+j]=dp[i]+1;
                 }
             }
           
        }
        printf("%d\n",dp[n]);
    }
    
    return 0;
}