题目的主要信息:

  • 给定一个非负整数数组,数组中每个元素值表示可以往后续跳跃的最大步数,即到达某个元素值时可以往后跳跃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(n2)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即可。

alt

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),没有使用额外辅助空间