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

题目主要信息

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

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

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

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

方法一：动态规划

具体方法

本题可以使用动态规划，设置一个dp数组，dp[i] 表示以所有i为结尾的数组所能达到的最大得分。

遍历数组，在每个数字的时候，可以遍历它能跳远的1-nums[i] 的长度，更新后续的dp数组，更新的公式为$dp[i+j]=max(dp[i+j],dp[i]+nums[i+j])dp[i+j]\; =\; max(dp[i+j],dp[i]+nums[i+j])$;其中其中i为数组下标，j为步幅。更新之后，后续可以被跳跃到的地方，其dp数组被更新后不再为-1了，因此再遇到-1说明到不了这个地方。

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxJumpGrade(vector<int>& nums) {
        // write code here
        // 判断是否为空
        if(nums.empty()){
            return -1;
        }
        //n保存数组的长度
        int len = nums.size();
        //值初始化为-1
        vector<int> dp(len,-1);
        dp[0] = nums[0];//初始化dp[0]
        for(int i = 0; i < len; i++) {//遍历一遍更新分数数组
            //这一步一定要判断 有一个测试用例为 11111 
            //如果该位置还是初始值，说明前面到达不了这里
            if(dp[i] == -1) 
                break;
               //continue;
            for(int j = i+1; j < nums.size() && j < i+nums[i]+1; j ++) {//遍历所有从i可以跳到的位置
                dp[j] = max(dp[j],dp[i] + nums[j]);
            }
        }
        return dp[len-1];
    }
};

复杂度分析

时间复杂度：$O\mathrm{（}{n}^2\mathrm{）}O（n^2）$，两层for循环

空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，dp数组的大小

方法二：贪心

具体方法

方法一需要遍历两层for循环，效率较低。

可以从后往前遍历，当一个位置index1可以跳到终点时，同时index2（index2<index1）也可以跳到终点时，那么index2的位置一定是可以跳到index1的位置，$nums[index2]+index2>=lennums[index2]+index2>=len$,而index1<=len,所以$nums[index2]+index2>=index1nums[index2]+index2>=index1$。如果index1为新的终点，那么求得分会是$nums[index1]+nums[index2]nums[index1]\; +\; nums[index2]$。

举例说明

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxJumpGrade(vector<int>& nums) {
        // write code here
         int len = nums.size();
        //数组长度为0，直接返回-1
        if(len==0) return -1;
        //当前积分
        int sum = nums[len-1];
         
        //当前跳跃的终点位置
        int index1 = len-1;
        for(int index2 = len-2;index2>=0;index2--){
            //只要能跳到curEnd位置，直接跟新积分值以及终点位置
            if(index2+nums[index2] >= index1){
                sum += nums[index2];
                curindex = index2 ;
            }
        }
        //如果最后能跟新到起始位置，直接返回grade，否则返回-1
        return index1 == 0?sum:-1;
    }
};

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，只需要遍历一次数组
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$，一个记录最终结果的变量