通过矩形网格的两条路径的最大赏金

Question

我正在尝试解决与此类似的问题 problem at GeeksforGeeks，但有所不同：
给定一个矩形二维网格，每个单元格中都有一些硬币值，任务是从左上角和右下角开始向右或向下，然后从右下角到左上角向左或向上，最大化拾取硬币的总数量。每个格子中的硬币只能被拾取一次。
link 中的解决方案是同时开始两个遍历，但这在这里行不通。
我应该如何解决这个问题？这样做的蛮力方法是枚举所有路径并选择两条路径，使所选硬币的总和最大化，但这不适用于大输入。

Answer 1

我不清楚您需要的 2 次遍历的确切要求，但对于任何给定的遍历，我都建议这样做。使用 Dijkstra 的算法，但构建它使得决定因素不是 2 个节点之间连接的 length/weight，而是使其成为网格正方形的值。确保它检查具有最大值而不是最小值的路径也很重要。

采用这种方法应该可以做到，如果有不止一种方法可以到达一个正方形（大多数情况下会有这种情况），算法将忽略除已累积最大值的路径之外的所有路径减少需要检查的路径数量。

例如：

输入：

int arr[R][C] = {{3, 6, 8},
                 {5, 2, 4},
                 {5, 1, 20},
                 {5, 1, 20, 10},
                };

开始： (0,0) 3

第一步：

    P1: (0,0) 3 , (1,1) 2 Total = 5
    P2: (0,0) 3 , (1,0) 5 Total = 8
both are still in the running for the best path.

第 2 步： P1 和 P2 都可以下一步到 (2,1) 1 在蛮力方法中你将有两条路径继续通过图形的其余部分但在这种方法中我们看到 P2 具有比 P1 更大的值所以没有需要继续 P1，然后从那个方块继续 P2。

Answer 2

我们可以通过三个观察来解决这个问题：

首先，不是从两个不同的点开始，我们可以反转第二个人的方向，这样问题就变成了两个人从左上角开始同时向右下角移动。
其次，如果我们假设两个人以相同的速度移动，那么这两个人的状态只能用三个参数来表示：x1, x2 and y1。由于我们可以很容易地根据第一个人的当前位置计算出他移动的次数（总和x1 + y1，因为他只能向右或向下移动），因此，我们也可以计算出第二个人的当前位置(y2 = x1 + y1 - x2)。请记住，两者都需要走相同的步数才能到达右下角，因此两者在任何给定时间内的移动次数都相同。
最后，我们应该注意到，一个人不能访问一个以上的位置，因为每个人只能走向右或向下的方向。此外，在任何状态下，每个人移动的次数是相等的，因此，如果存在两个人访问过的位置，他们将同时访问该位置（并且仅当x1 = x2时），这样一来，我们就可以轻松统计收集到的硬币数量了。

根据这些观察结果，可以很容易地将其简化为与 OP link:

中的问题类似的问题

从状态(x1, x2, y1)开始，由于每个人只能向右或向下移动，我们将有以下状态：

 (x1 + 1, x2 + 1, y1) : Both move to the right.
 (x1 + 1, x2, y1) : First person move right, second move down
 (x1, x2 + 1, y1 + 1) : First move down, second move right
 (x1, x2, y1 + 1) : Both move down.

所以，我们有我们的动态规划公式：

dp[x1][x2][y1] = coin[x1][y1] + (x2 != x1 ? coin[x2][y2] : 0 ) + max(dp[x1 + 1][x2 + 1][y1], dp[x1 + 1][x2][y1], dp[x1][x2 + 1][y1 + 1], dp[x1][x2][y1 + 1])

通过矩形网格的两条路径的最大赏金

Maximum bounty from two paths through a rectangular grid

algorithm

graph-algorithm

path-finding