穿越矩阵收集最高金额的路线

因此，我在翻阅一本书时偶然发现了一个有趣的问题。给你一个N * M矩阵，你必须从坐标（1,1）到（n，m）。穿越矩阵收集最高金额的路线

给出三种类型的“操作”来与矩阵交叉。

'A'- You go from i,j to i+1,j 

'B'- You go from i,j to i,j+1 

'C'- You go from i,j to i+1,j+1

每当你穿过一个元素，你就把它添加到你的“总和”中。您被要求：

我没有问题解决（1）与动态编程，但（2）把我放在一个泡菜。该书对第（2）点没有任何解释。想知道你们之前是否遇到过类似的事情。

2014-02-06 Sid Wit

econstruct的意思是什么意思呢？一系列的A，B＆C？ –

您可以将问题简化为DAG中的最短路径问题（根据定义，它没有负循环），只需使用Bellman-Ford算法在“-1 * X”（“X”是您的矩阵）上找到最短路径。 – amit

@amit Belman-Ford也是动态规划方法。这只是一个受欢迎的。我不是说你的评论是错误的，但我只是说OP可能会使用它（没有意识到）。与Bellman-Ford一起恢复解决方案与我相信的任何其他DP一样困难（并且在所有恕我直言中都不那么困难）。 –

DP的一般经验法则：如果除了获得最佳值之外还需要重构最优解，请使用第二个数组。第二个数组的大小应与您存储子问题答案的大小完全相同。然而，在这个数组中，不是存储答案，而是存储导致最优解的子问题的一些标识。在你的情况下，标识将是A，B或C，以指示你已经做出了哪一步。

2014-02-06 13:45:35

您可以仅使用子问题解决方案阵列（我们称之为D）重建路径本身，而无需任何额外的阵列。从(n, m)到(1, 1)只是倒退使用以下规则：

您可以轻松地证明（记住具有
D[i][j] = M[i][j] + max(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])，
其中M是初始矩阵），这将导致你到（1,1），以及所产生的序列是最大和路径确实。

2014-02-06 14:09:45 Tenente

回答