每次迭代返回正确的值-动态规划

Question

问题是这样的：

极客要去参加n天的培训项目。他可以执行跑步、战斗和学习练习这三种活动中的任何一种。每项活动每天都有一定的意义。由于 Geek 想要提高他所有的技能，他不能连续两天做同样的活动。帮助 Geek 最大化他的优点积分，因为您将获得与每天和活动相对应的二维积分数组。

现在这就是我正在尝试的方法。我获取数组的每个值，并在传递前一个索引的同时递归调用下一个索引，以便在计算中跳过其值。

我弄错了，因为我正在返回

this.currentMax

，它不断添加到

points[index][j]

，而我更想要的是在每一步中，计算仅针对该迭代进行，并且如果它大于

this.currentMax

后者应该得到更新。我该如何纠正这个问题？感谢任何帮助。

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))

编辑： @Bergi 的建议有效。但这仍然让我困惑。当我们创建一个局部变量maxPoint时，下一个递归调用不应该一次又一次地将这个变量重置为0。

例如，

f(([[1,2,5], [6, 2, 10]], 2, index=0, prev=-1)

会生成

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

但是在每个调用中，maxPoint都会更新为返回的最大值和0（因为每次都会重置而为零？）

感谢澄清：

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))

Answer 1

正如您所指出的，直接的问题是，当您回溯递归时，

this.currentMax

不断被添加并且永远不会回滚到以前的值，因此它表示递归树的多个分支的值的总和。

第一个要考虑的解决方案是将

currentMax

作为参数传递：这样它就成为一个局部变量，不会影响调用者的同名变量。

但是接下来我们遇到了其他问题：

该算法搜索所有可能的可以建立的路径。由于代码挑战可能会向您传递一个包含多达十万个条目的数组，因此您将尝试访问 2¹⁰⁰⁰⁰⁰ 状态，即使您让 PC（或最快的超级计算机）在其余时间保持运行，这实际上也是不可能的一生。

您可以通过使用记忆来防止这种指数爆炸。

但是随后您就会遇到调用堆栈的限制。 JS 调用栈的限制可能不支持 100000 的深度。所以你应该将算法转换为迭代算法：

迭代算法

你可以应用这个逻辑：

当我们在

index

结束并选择最后一个活动 0、1 或 2 时跟踪最佳结果：因此我们有三个“最佳结果”。

当

index

增加时，这些最佳值可以更新如下：

• 选择活动 0：采用

  points[0]

  并添加我们之前活动 1 和 2 的最佳成绩的最大值
• 类似地，我们可以确定索引

  index

  处其他活动的最佳值，因此我们得出三个更新的最佳值，每个活动一个。

这是基于该方法的剧透实现：

    maximumPoints(points, n) {
         let dp = points[0];
         for (let index = 1; index < n; index++) {
             const [a, b, c] = points[index];
             dp = [
                 a + Math.max(dp[1], dp[2]),
                 b + Math.max(dp[0], dp[2]),
                 c + Math.max(dp[0], dp[1]),
             ];
         }
         return Math.max(...dp);
     }