查找矩阵路径来获得最大的价值

Question

我知道，这是一个老问题，如果给像矩阵：

[1 1 2 3， 
2 3 4 4， 
3 4 1 3， 
2 1 3 4] 

开始在给定的位置，从右到左，只有移动向右，向上或或者向下，不能以相同的方式返回并停在正确的位置，找到获得最大值的路径。

我正在考虑使用DP（可能需要尝试所有可能的路径和计算值），但它似乎会花费大量内存，因为它存储所有可能的解决方案，也可能会很慢。

我想知道是否有任何其他的想法或方法来作出更好的解决方案？如果可能，更快的解决方案？

Answer 1

我认为有一种方法做一个DP，我只是不能很快地找到它。因为目前为止没有人回答它，所以我会给出一个图表方法。创建一个有向图，其中从A到B的边将等于该顶点中的数。从您的描述中可以清楚的看到它不会有任何循环。你会得到一个网格图这个样子，但只针对：

现在得到一个顶点来源，在右边的地方，并把它连接到第一层（把所有的边缘等于0）。与目的地相同，但位于左侧。

现在运行longest path in directed acyclic graph

Answer 2

如果你想优化内存，你可以尝试回溯。这只涉及存储当前路径，还有最佳解决方案的路径和值。

大纲是：

1. 您存储的步骤列表（右，上，下）
2. 你去深度优先这么说，尽量让一个新的台阶，如果你能
3. 如果你不能，只需回去一步，改变下一个可能的方向。 （如果它比先前存储的更好，则存储此路径）。
4. 如果该步骤没有下一个可能的方向，请重复3.
5. 如果所有可能性都耗尽，请返回存储的最佳路径。

回溯在维基百科：https://en.wikipedia.org/wiki/Backtracking