如何通过一个网格采取的路径时，计算最高分？ [英] How to calculate the highest score when taking a path through a grid?

问题描述

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

We have a 3x3 grid with the following values:
1 3 4
7 2 1
4 1 8

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

A person starts on the leftmost column and can then move either northeast, east or southeast. Now I have to find the optimal path through this grid. The starting point can be anywhere on the leftmost column. In this case the answer was 17 because the optimal path was 7->2->8. I would like to know how to compute this optimal path and how to compute it for larger grids.

谢谢！

推荐答案

您可以解决这个问题，一个自下而上的方法，或者更确切地说，从右到左在这种情况下。

You can solve this problem with a bottom-up approach, or rather right-to-left in this case.

最后一列是路径的结束点。现在考虑第二，但最后一排。您可以从每个小区确定潜在的得分 S [I] [J] 由细胞的得分 A [1] [J] 加上相邻小区的最大潜力得分，东：

The last column is the end point of the path. Now consider the second but last row. You can determine the potential score from each cell s[i][j] by the cell's score a[i][j] plus the maximum potential score of the adjacent cells to the east:

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

如果你这样做，对电池再往西，你认为细胞已经累积值进一步东部。最大比分的最佳路径开始在第一列中的最大累积值取值。从那里，你所挑选最好的相邻值往东走。

If you do that for cells further to the west, you consider the already accumulated values of the cells further east. The optimal path with maximum score starts at the maximum accumulated value s in the first column. From there you go east by picking the best adjacent value.

累计矩阵取值为您的例子是：

The accumulated matrix s for your example is:

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

此方法，你由右至左积累的最佳本质上是一样的，从左至右在已计算值memoized在取值。

This approach where you accumulate the optimum from right to left is essentially the same as working from left to right where already calculated values are memoized in s.

这篇关于如何通过一个网格采取的路径时，计算最高分？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！