LeetCode跳跃游戏4记忆化递归错误排查

给定0-indexed整数数组nums和整数k：
初始站在索引0位置，单次移动最多可向前跳k步且不能超出数组边界，即从索引i可跳到范围[i + 1, min(n - 1, i + k)]内的任意索引。目标是到达数组最后一个索引（索引n-1），路径得分为经过的所有索引j对应的nums[j]之和，请返回可获得的最大得分。

示例1 #

• 输入：nums = [1,-1,-2,4,-7,3], k = 2
• 输出：7
• 解释：可选择跳跃路径形成子序列[1,-1,4,3]，总和为7。

初始暴力递归版本 #

你最开始写的递归版本逻辑是正确的，但是时间复杂度是指数级，数据量稍大就会超时，代码如下：

class Solution {
    
    static int min= Integer.MIN_VALUE;
    
    public int maxResult(int[] nums, int k) {
        return max(nums,0,k,0);
    }
    
    public int max(int [] nums, int ind, int k, int curSum)
    {  
        if(ind==nums.length-1)
            return curSum+nums[ind];
   
        int max=Integer.MIN_VALUE;
        
        for(int i=ind+1;i<=Math.min(nums.length-1,ind+k);i++)
            max=Math.max(max, max(nums,i,k,curSum+nums[ind]));
         
        return max;
    }
}

记忆化版本错误原因 #

加了dp数组之后结果错误，核心原因是dp缓存的定义和递归函数的返回值不匹配：

• 记忆化数组dp[ind]的设计目标应该是存储固定值：从索引ind出发，走到终点能拿到的最大路径和。这个值只和ind位置有关，和你通过什么路径走到ind没有关系。
• 但你当前的递归函数传入了curSum参数，这个值是走到ind之前已经累加的路径分数，不同路径走到同一个ind时，curSum可能完全不同。你第一次递归到ind时，把带着当时curSum算出的结果存进dp[ind]，后续其他路径走到ind时直接返回这个缓存值，相当于把第一条路径的前缀和强行套到所有到ind的路径上，结果必然错误。

举个简单的例子：走到索引2有两条路径，第一条到2时累计分数是-3，第二条到2时累计分数是0。如果第一次递归走的是-3的路径，你存的dp[2] = -3 + 从2出发的最大得分，后面累计0的路径到2时直接返回这个dp值，平白少了3分，结果肯定不对。

1. 调整递归函数逻辑，去掉curSum参数，让函数返回值严格匹配dp的定义：即从ind出发到终点的最大得分。递归关系可以直接写成dp[ind] = nums[ind] + max(dp[ind+1], dp[ind+2], ..., dp[min(ind+k, n-1)])，边界条件是dp[n-1] = nums[n-1]。
2. 递归加记忆化的时间复杂度是O(nk)，如果n和k的量级到1e5还是会超时，可以进一步用单调双端队列维护长度为k的滑动窗口内的dp最大值，把时间复杂度降到O(n)。

内容的提问来源于stack exchange，提问作者BosssMan861