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

题目的主要信息：

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

方法一：

暴力计算。dp数组为得分数组，dp[i]表示第i个位置最大得分。遍历一遍原始数组nums用来更新dp数组，遍历更新从i位置开始所有可以跳到的位置j的最大得分，dp[j] = max(dp[j],dp[i] + nums[j])。这样遍历一遍后dp[n-1]即为跳到最后一位可以得到的最大得分。

具体做法：

class Solution {
public:
    int maxJumpGrade(vector<int>& nums) {
        if(nums.empty()){//数组为空
            return -1;
        }
        int n = nums.size();//n保存数组的长度
        vector<int> dp(nums.size(),-1);//分数数组，值初始化为-1
        dp[0] = nums[0];//初始化dp[0]
        for(int i = 0; i < n; i++) {//遍历一遍更新分数数组
            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[n-1];
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，最坏情况下，双层for循环时间复杂度为$O(n^2)O(n^2)$。
• 空间复杂度：$O(n)O(n)$，dp数组的大小为n。

方法二：

动态规划。动态数组dp，dp[i]表示从i位置跳到末尾的最大得分，首先初始化动态数组，将dp[i]初始化为位置i处的分数。要想找到从开头到末尾积分最大的跳跃路径，应该从后往前更新动态数组，用pos记录可以跳到末尾的最小位置，遍历一遍dp数组更新，如果最后pos不为0，表示从开头无法跳到最后一个位置。 具体做法：

class Solution {
public:
    int maxJumpGrade(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {//数组为空，返回-1
            return -1;
        }
        vector<int> dp(n, 0);//动态数组，dp[i]表示从i位置跳到末尾的最大得分
        for(int i = 0; i < n; i++) {//初始化动态数组
            dp[i] = nums[i];
        }
        int pos = n - 1;//pos表示可以跳到末尾的最小位置
        for(int i = n - 2; i >= 0; i--){//从末尾往前更新动态数组
            if(i + nums[i] >= pos){//如果从i可以跳到pos
                dp[i] = dp[pos] + nums[i];//i跳到pos再跳动末尾比pos跳到末尾多了i的积分
                pos = i;//更新pos的位置
            }
        }
        if(pos == 0){//如果pos为0说明可以从0跳到末尾
            return dp[0];
        }
        return -1;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一层for循环。
• 空间复杂度：$O(n)O(n)$，dp数组的大小为n。