动态规划递归修正：每日活动不重复的最大积分问题答疑

Geek 参加一个n天的训练计划，每天可选择跑步（Running）、格斗（Fighting）、学习训练（Learning Practice）三项活动之一，每项活动在不同日期对应不同积分。要求连续两天不能进行同一活动，需根据给定的二维积分数组points，计算Geek能获得的最大总积分。

初始解法问题 #

我尝试用递归方法：遍历每日的活动积分，递归调用下一日的计算并传递前一日的活动索引以跳过重复活动。但返回类成员变量this.currentMax时出错了——这个变量会被累加至points[index][j]，而我需要的是每步仅针对当前迭代计算，若结果更大则更新最大值。初始错误代码如下：

class Solution {
    //Function to find the maximum points among all the possible ones.
    currentMax = -Infinity;
    maximumPoints(points, n, index=0, prev=-1)
    {
        if(index === n) return 0;
        for(var j=0; j<points[index].length; j++){
          //skip the prev index
          if(j !== prev){
           var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
           
           this.currentMax = Math.max(this.currentMax, temp);
           
          }
            
         }
        
        return this.currentMax //This is where perhaps going wrong
    }
}

var x = new Solution();
console.log(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))

修正后的疑问 #

采纳建议改用局部变量maxPoint后代码能正常运行，但我有个疑问：每次递归调用都会把maxPoint重置为0，比如调用maximumPoints([[1,2,5], [6, 2, 10]], 2, index=0, prev=-1)会生成以下分支：

1 + maximumPoints([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
2 + maximumPoints([[1,2,5], [6, 2, 10]], 2, index=1, prev=1)
5 + maximumPoints([[1,2,5], [6, 2, 10]], 2, index=1, prev=2)

为什么每次调用里的maxPoint能正确更新，不会被重置影响？修正后的代码如下：

class Solution {
    //Function to find the maximum points among all the possible ones.
   
    maximumPoints(points, n, index=0, prev=-1)
    {
        if(index === n) return 0;
        let maxPoint = 0;
        
        for(var j=0; j<points[index].length; j++){
          //skip the prev index
          if(j !== prev){
           var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
           
           maxPoint = Math.max(maxPoint, temp);
           
          }
            
         }
        
        return maxPoint;
    }
}

var x = new Solution();
console.log(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))

疑问解答 #

核心原因是每个递归调用都拥有独立的函数执行上下文，局部变量maxPoint绑定在当前调用的上下文里，不同递归调用之间的maxPoint完全互不干扰：

1. 当进入最外层调用（index=0）时，会创建一个局部的maxPoint初始化为0，然后循环j=0、1、2：

   • j=0时，递归调用index=1、prev=0，这个新调用会创建自己的maxPoint初始化为0，循环j=1、2（跳过prev=0），计算出该分支的最大积分是10，返回给外层后，外层计算1+10=11，和当前maxPoint（0）比较，更新为11。
   • j=1时，递归调用index=1、prev=1，这个调用自己的maxPoint初始化为0，循环j=0、2，计算出最大积分是10，外层计算2+10=12，和当前maxPoint（11）比较，更新为12。
   • j=2时，递归调用index=1、prev=2，这个调用自己的maxPoint初始化为0，循环j=0、1，计算出最大积分是6，外层计算5+6=11，和当前maxPoint（12）比较，不更新。
   • 最后外层返回12，就是正确的最大积分。

2. 每个递归调用的maxPoint都是独立的局部变量，重置只发生在自己的调用上下文里，不会影响其他层级的调用。而之前用类成员变量this.currentMax时，所有递归调用共享同一个变量，不同分支的结果互相覆盖累加，才会导致错误。

内容的提问来源于Stack Exchange，提问作者ABGR