algorithm - 如何计算通过网格的路径时的最高分？

Question

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

一个人从最左边的一列开始，然后可以向东北、向东或东南方向移动。现在我必须找到通过这个网格的最佳路径。起点可以是最左边一列的任何位置。在这种情况下，答案是 17，因为最佳路径是 7->2->8。我想知道如何计算这条最佳路径以及如何针对更大的网格计算它。

谢谢!

Answer 1

您可以使用自下而上的方法解决此问题，在本例中更确切地说是从右到左。

最后一列是路径的终点。现在考虑第二行也是最后一行。您可以通过单元格的得分 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 中内存的方式基本相同。