找到路径交叉矩阵,最大值前向然后向后
如果我有一个矩阵,矩阵的每个元素都是一个非负数.我想从左下角到右上角穿过矩阵.在每一步中,我只能向上或向右移动,每个被访问的元素将被设置为0; 之后,我从右上角走到左下角,每一步我都只能向下或向左移动.
我的问题是如何有效地找到具有最大总和的路径.
让我们有一个包含N行和M列的矩阵，并假设N>=2和M>=2，否则解决方案很简单。我有一个O(max(M,N) * min(N,M)^4)使用动态编程的算法。
首先，让我们证明始终存在路径不交叉的最佳解决方案（在起点和终点除外）。我们将采用任何解决方案并将其转换为不交叉的解决方案，而不会降低优化功能。
证明：
首先，确保第二条路径（从右上到左下）始终在第一条路径的上方或同一行。为此，请在两条路径的单个部分中找出不正确的地方，然后交换它们。插图：
然后，一次消除一个碰撞。您总是可以找到一条碰撞，至少有一条路线在那儿转弯，并且您可以更改该路线以避免碰撞。重复此过程，直到所有碰撞都被消除。第一步说明：
我们看到，不仅没有从两个路径中删除的元素相结合，而且还添加了更多元素，并且所有元素都是非负数，所以总和只能增加。
算法：
我们将只考虑不交叉的路径，我还要假设N<=M（矩阵宽度至少与高度相同）。通常，我们会从一列中添加数字，使用Prefix sum可以快速完成。
我们将从第一列开始。对于每对（i，j），1<=i<j<=N我们将计算该对的分数，即两条路径从（1,1）到（1，i）和（1，j）的总和） 分别。例：
Matrix:
1 2 3
4 5 6
7 8 9
score(1,1) = 7
score(1,3) = 12
score(2,3) = -inf (paths cannot cross)
然后，我们将根据当前列中的对分数计算下一列中每对的分数。对于下一列中的每个对，只需查看上一列中所有其路径可以扩展以匹配当前列的路径的对。
最后，您的答案是(N-1, N)最后一列中对的分数。我很抱歉在书面媒体上解释算法很糟糕，我希望它不会完全不稳定。