如何计算通过网格的路径时的最高分？
How to calculate the highest score when taking a path through a grid?
我们有一个具有以下值的 3x3 网格：
1 3 4
7 2 1
4 1 8
一个人从最左边的一列开始，然后可以向东北、向东或东南方向移动。现在我必须找到通过这个网格的最佳路径。起点可以是最左边一列的任何位置。在这种情况下，答案是 17，因为最佳路径是 7->2->8。我想知道如何计算这个最佳路径以及如何计算更大的网格。
谢谢！
这是longest path problem in a graph. While generally it is a hard problem to solve, your graph is a Directed Acyclic Graph, so it becomes much simpler to solve it with Dynamic Programming。
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)时间内找到所有D(x,y)（如果不是方阵则为O(n*m)），然后简单地迭代D(n-1,y)找到最大值。
您可以使用自下而上的方法解决此问题，在本例中更确切地说是从右到左。
最后一列是路径的终点。现在考虑第二行也是最后一行。您可以通过单元格的分数 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 中记忆的方法基本相同。
我们有一个具有以下值的 3x3 网格：
1 3 4
7 2 1
4 1 8
一个人从最左边的一列开始，然后可以向东北、向东或东南方向移动。现在我必须找到通过这个网格的最佳路径。起点可以是最左边一列的任何位置。在这种情况下，答案是 17，因为最佳路径是 7->2->8。我想知道如何计算这个最佳路径以及如何计算更大的网格。
谢谢！
这是longest path problem in a graph. While generally it is a hard problem to solve, your graph is a Directed Acyclic Graph, so it becomes much simpler to solve it with Dynamic Programming。
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)时间内找到所有D(x,y)（如果不是方阵则为O(n*m)），然后简单地迭代D(n-1,y)找到最大值。
您可以使用自下而上的方法解决此问题，在本例中更确切地说是从右到左。
最后一列是路径的终点。现在考虑第二行也是最后一行。您可以通过单元格的分数 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 中记忆的方法基本相同。