我们有一个3x3的网格,具有以下值:
1 3 4
7 2 1
4 1 8
1 3 4
7 2 1
4 1 8
一个人从最左侧的列开始,然后可以向东北、东或东南移动。现在我必须找出这个网格中的最佳路径。起点可以在最左侧的任何列。在本例中,答案是17,因为最佳路径是7->2->8。我想知道如何计算这个最佳路径,并如何计算更大网格的最佳路径。
谢谢!
一个人从最左侧的列开始,然后可以向东北、东或东南移动。现在我必须找出这个网格中的最佳路径。起点可以在最左侧的任何列。在本例中,答案是17,因为最佳路径是7->2->8。我想知道如何计算这个最佳路径,并如何计算更大网格的最佳路径。
谢谢!
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
中的方法本质上是相同的。