DP27 跳跃游戏(二)

题解：首先确定可不可以到达最后一个位置：

1、如果不可以直接返回结果-1；

2、如果可以用dp求到达最后一个位置的最大积分：dp[i]表示到达位置i的最大积分；

//id表示可以到达的最大位置坐标,i表示当前位置

if(id>=i)

{

dp[i]=dp[i]+num[i];

if(num[i]+i>id)

     id=num[i]+i;

}

  for(int j=1;j<=num[i];j++)
   {
                dp[i+j]=max(dp[i],dp[i+j]);//表示dp[i+j]表示i+j到达位置的最大积分
     }

详情请看代码

描述

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。

1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1

2.如果无法跳跃(即数组长度为0)，也请返回-1

3.数据保证返回的结果不会超过整形范围，即不会超过

输入描述：

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

第二行输入 n 个整数，表示数组 nums 的所有元素的值

输出描述：

输出能获得的最多的积分

示例1

输入：

6
2 4 2 1 0 100

复制输出：

106

复制说明：

首先位于nums[0]=2，然后可以跳1步，到nums[1]=4的位置，积分=2+4=6，再跳到nums[5]=100的位置，积分=6+100=106
这样保证既能跳到数组最后一个元素，又能保证获取的积分最多    
 

示例2

输入：

6
2 4 0 2 0 100

复制输出：

108

复制说明：

跳跃路径为：2=>4=>2=>100，总共为108        

示例3

输入：

6
2 3 2 1 0 100

复制输出：

-1

复制说明：

跳不到最后一个位置，返回-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 step=0;
    //dp[i]走到第i位置获得的最大积分
    dp[1]=num[1];
    step=num[1]+1;
    int t=0;
    for(int i=2;i<=n;i++)
    {
        
        if(step>=i)
        {
            if(i+num[i]>=step || i+num[i]>=n)
            {
                step=i+num[i];
             }
         }
        else{
            t=1;
            break;
        }
    
    }
    //不能到达最后一个位置
    if(t || step<n)
    {
        printf("-1\n");
        return 0;
    }
    else{//可以到达最后一个位置，用dp求最大积分
        int id=0;
        for(int i=1;i<=n;i++)
        {
            if(i==1)
            {
                dp[i]=num[i];
                id=num[i]+1;
            }
            else{
                if(id>=i)
                {
                    dp[i]=dp[i]+num[i];
                    int m=i+num[i];
                    if(m>id)
                    {
                        id=m;
                    }
                }
                
            }
            for(int j=1;j<=num[i];j++)
            {
                dp[i+j]=max(dp[i],dp[i+j]);
            }
        }
        printf("%d\n",dp[n]);
    }
   
    return 0;
    
    
    
    
    
}