题解 | #跳跃游戏(二)#

描述 给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。 1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1 2.如果无法跳跃(即数组长度为0)，也请返回-1 3.数据保证返回的结果不会超过整形范围，即不会超过231−12^{31}-1231−1 数据范围: 0<=nums.length<=1050<=nums.length<= 10^50<=nums.length<=105 0<=nums[i]<=1000 0<=nums[i]<=1000\ 0<=nums[i]<=1000

输入描述： 第一行输入一个正整数 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<vector>

using namespace std;

class Solution {

    public:
    int upgame2(vector<int> &nums){
        
       if (nums.size()==0){
           return -1;
       }
        vector<int>dp(nums.size(),0);
        dp[0] = nums[0];
        
        for (int i =0;i< nums.size();i++){
            for (int j = i+1; j<= i + nums[i] && j<nums.size();j++){
                    dp[j] = max(dp[j] , dp[i] + nums[j]);
              
            }
        }
        
//           for (int i =1;i< nums.size();i++){
//             for (int j = 0;j<i;j++){
//                 if(j + nums[j] >= i){    
//                 dp[i] = max(dp[i] , dp[j] + nums[i]);
//                 }
//             }
//         }
        
        return dp[nums.size()-1]==0 || dp[nums.size()-1]==80000  ?-1:dp[nums.size()-1];
        
        
    }
     int upgame2plus(vector<int> &nums){
        vector<int>dp(nums.size(),0);
        dp[0] = nums[0];
        
        for (int i =0;i< nums.size();i++){
            for (int j = i+1; j<= i + nums[i] && j<nums.size();j++){
                    dp[j] = max(dp[j] , dp[i] + nums[j]);
              
            }
        }
        
//           for (int i =1;i< nums.size();i++){
//             for (int j = 0;j<i;j++){
//                 if(j + nums[j] >= i){    
//                 dp[i] = max(dp[i] , dp[j] + nums[i]);
//                 }
//             }
//         }
        
        return dp[nums.size()-1];
        
        
    }
    
};
int main (){
    
    int n,val;
    cin >> n;
    vector<int> nums(n);
    for (int i =0;i< n;i++){
        cin >>val;
        nums[i] = val;
    }
    
    Solution solu;
    cout <<solu.upgame2(nums)<< endl;
    return 0;
}