如何计算在网格中通过路径时的最高得分？

Question

我们有一个3x3的网格，具有以下值：
1 3 4
7 2 1
4 1 8

一个人从最左侧的列开始，然后可以向东北、东或东南移动。现在我必须找出这个网格中的最佳路径。起点可以在最左侧的任何列。在本例中，答案是17，因为最佳路径是7->2->8。我想知道如何计算这个最佳路径，并如何计算更大网格的最佳路径。

谢谢！

- Luto

---

终点在哪里（右列，右下角，...）？最优路径是总和最小的路径吗？ - Fernando Matsumoto

终点可以位于最右侧的任何一列，而最佳路径是总和最高的路径。 - Luto

Answer 1

这是图中的最长路径问题。虽然通常很难解决，但您的图是有向无环图，因此使用动态规划解决它变得更加简单。

D(x,-1) = -infinity       
D(x,n)  = -infinity        
D(-1,y) = 0
D(x,y) = max { D(x-1,y), D(x-1,y-1), D(x-1,y+1) } + value[x][y]

这里的想法是，D(x,y)表示从左侧列开始并以坐标(x,y)结束的最短路径值。

使用动态规划，您可以在O(n^2)时间（如果不是方阵，则为O(n*m)）内找到所有D(x,y)，然后只需迭代D(n-1,y)即可找到最大值。

- amit

Answer 2

你可以采用自下而上的方法，或者在这种情况下采用从右到左的方法来解决这个问题。

最后一列是路径的终点。现在考虑倒数第二行。您可以通过单元格得分a[i][j]加上东侧相邻单元格的最大潜在得分来确定每个单元格s[i][j]的潜在得分。

s[i][j] = a[i][j] + max(s[i - 1][j + 1], s[i][j + 1], s[i + 1][j + 1])

如果您要翻译西边更远的单元格，则要考虑已经累加的东边单元格的值。具有最大分数的最优路径始于第一列中的最大累积值s。从那里开始，您可以通过选择最佳相邻值向东前进。

您的示例的累积矩阵s如下：

    | 1  3  4 |            | 11  7  4 |
a = | 7  2  1 |        s = | 17 10  1 |
    | 4  1  8 |            | 14  9  8 |

从右到左累积最优解的方法与从左到右计算并将已计算值存储在 s 中的方法本质上是相同的。

- M Oehm

---

谢谢！我实现了这个累积矩阵系统，现在一切都正常工作。 - Luto