algorithm - 如何使用两条不同的路径遍历网格以使路径之和最大化？

Question

我有一个 N 乘 N 的网格，每个框中都有值。我必须从左上角移动到右下角(路径 1)以及从右上角移动到左下角(路径 2)。当我从左上角移动到右下角时，我只能向下或向右移动。同样，当我从右上角移动到左下角时，我只能向左和向下移动。

但是如果我在选择路径 1 时向下移动，则路径 2 的相应移动应该是向左移动。同样，如果我在选择路径 1 时向右移动，则路径 2 的相应移动应该向下。

当我们采用两条路径时，我们将在每个框中遇到的值相加。我们可以获得的最大值是多少？

以下面的网格为例:

 6   0   3  -1

 7   4   2   4

-3   3  -2   8

13  10  -1  -4 

我们可以采用的最佳路径表示如下:路径一用 * 表示，而路径 2 用 ~ 表示。

(6*)  (0)   (3~)  (-1~)

(7*)  (4*~) (2~)  (4)

(-3)  (3*~) (-2*) (8*)

(13~) (10~) (-1)  (-4*)

这两条路径的总和是 56。

我们必须设计一种算法来计算给定任意 N × N 网格的最大可能分数。

很明显这是一个 DP 问题。所以，我试图确定一个递归关系，可以这么说。我尝试使用经典问题中的递推关系，即在 N × M 网格中查找所有路径的最大总和，但这没有用，因为它变得太复杂了。

我尝试将 N × N 网格划分为四个 (N-1) × (N-1) 重叠的网格，因此在 3 × 3 网格中进行演示:

a1 a2 a3

a4 a5 a6

a7 a8 a9

我把它分成四个 2 x 2 的网格:

a1 a2  ,   a2 a3   ,   a4 a5   ,  a5 a6

a4 a5  ,   a5 a6   ,   a7 a8   ,  a8 a9

假设我们知道所有这些网格的最佳路径，那么我们可以计算更大网格的最佳路径吗？

嗯，这看起来很有希望，但我很快发现这些递归关系取决于更大的情况。例如，

如果我们考虑第二个 2 x 2 网格，假设我们知道最佳路径 1 和路径 2 = S。现在，显然，要从 a1 到 a2，我们需要向右移动，但这意味着子案例中的第一步(路径 2 中的第一步)应该向下移动，但不能保证。

我们如何解决这个问题？

Answer 1

移动两点的规则等同于通过网格找到一条路径，该路径是您的网格和自身旋转 -90 度的总和(向左/逆时针/逆时针旋转 90 度，具体取决于您的语言环境).

左上角的“向下”对应于右上角的“左”，旋转-90度时向下。左上角的“右”对应于右上角的“下”，旋转-90 度时为右。 (明白了吗？)

所以你的示例网格是

 6-1   0+4   3+8  -1-4        5   4  11  -5

 7+3   4+2   2-2   4-1       10   6   0   3
                          =
-3+0   3+4  -2+3   8+10      -3   7   1  18

13+6  10+7  -1-3  -4+13      19  17  -4   9

您现在可以通过任何常用方法找到从左上角到右下角的路径。事实上，您不需要路径，只需要最大和，这更容易:通过加法从左上角向下折叠矩阵。初始条件是上面的网格。下一步是将左上角的值添加到它的有效邻居中:

     9  11  -5

15   6   0   3

-3   7   1  18

19  17  -4   9

然后为任何具有两个有效邻居的网格点选择两个邻居中较大的一个(这里 21 大于 20 和 12):

        20  -5

    21   0   3

12   7   1  18

19  17  -4   9

等等……

            15

        21   3              24
                ->                  
    28   1  18           29 18     ->        47
                                                    ->  
31  17  -4   9        48 -4  9            44  9            56

我刚刚手工解决了你的 4x4 问题，答案是 56。