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

题目的主要信息：

• 给定一个非负整数数组，数组中每个元素值表示可以往后续跳跃的最大步数，即到达某个元素值时可以往后跳跃1到该值之间任意步数
• 需要从数组第一个元素跳到数组最后一个元素，其中每经过一个元素，该元素的值作为积分，求最大积分值
• 如果数组为空或者到达不了末尾返回-1

方法一：动态规划

具体做法：

可以使用动态规划，创建一个数组，其中dp[i]表示到达下标为i的末尾元素能够达到的最大积分，全部初始化为-1.很明显，dp数组边界值第一个元素就是原数组的第一个元素值。

后续遍历数组，补全dp数组。在遍历过程中，到达某个元素，可以遍历它要跳跃的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:
    int maxJumpGrade(vector<int>& nums) {
        if(nums.size() == 0) //排除空数组
            return -1;
        vector<int> dp(nums.size(), -1); //初始化所有位置的积分都为0
        dp[0] = nums[0]; //第一格的积分肯定是第一个元素值
        for(int i = 0; i < nums.size(); i++){ //遍历整个数组，获取每个位置的积分
            if(dp[i] == -1) //如果该位置还是初始值，说明前面到达不了这里
                continue;
            for(int j = 1; j <= nums[i] && i + j < nums.size(); j++) //遍历跳跃步幅从1到最大值
                dp[i + j] = max(dp[i + j], dp[i] + nums[i + j]); //更新后续的积分值
        }
        return dp[nums.size() - 1];
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，两层循环，两次遍历到$nn$
• 空间复杂度：$O(n)O(n)$，动态规划辅助数组的长度为$nn$

方法二：贪心

具体做法：

动态规划从前往后很复杂，我们也可以从后往前遍历。从前往后的时候，某个点可以到达结尾，从后往前的时候同样也是这个道理。而且如果当前的位置i可以到达数组结尾，同时前面的位置j也可以到达数组结尾，那我们可以考虑替换i为新的结尾（i肯定在最开始结尾前面），只要从j到i再走一步，那积分值会加上$nums[i]+nums[j]nums[i]+nums[j]$，比从j直接到数组结尾会多经过更多地方，积分也会更高。

因此从后往前的时候，我们用贪心思想，尽可能多经过数组格子，一旦某个地方的值加起来能够到达结尾，我们就更新它为新的结尾，然后累加上这个地方的积分，直到到达开头。当然如果到不了开头，说明正向也无法到达结尾，返回-1即可。

class Solution {
public:
    int maxJumpGrade(vector<int>& nums) {
        if(nums.size() == 0) //排除空数组
            return -1;
        int res = 0;
        int pos = nums.size() - 1; //目标位置从结尾到开头
        for(int i = nums.size() - 1; i >= 0; i--){ //逆向查找
            if(i + nums[i] >= pos){ //每次加起来能够到达这个位置
                pos = i; //更新前序位置
                res += nums[i]; //增加积分
            }
        }
        if(pos != 0) //没有达到开头，说明正向也到不了结尾
            return -1;
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，从后往前一次遍历
• 空间复杂度：$O(1)O(1)$，没有使用额外辅助空间