通过一个矩形网格的两个路径获得的最大奖励

Question

我正在尝试解决类似于GeeksforGeeks上的这个问题，但有所不同：（参考链接）
给定一个矩形2D网格，每个单元格中都有一定数量的硬币价值。任务是从左上角和右下角开始向右或向下移动，并从右下角到左上角向左或向上移动，最大化收集的硬币总价值。每个单元格中的硬币仅能被收集一次。
该链接中的解决方案是同时开始两个穿越路径，但这种方法在这里不适用。
我应该如何解决此问题？ 暴力枚举所有路径并选择两条使得硬币总价值最大的路径可能行不通，因为输入规模很大。

- Prashant Bhanarkar

---

抱歉，也许我没有理解正确。您必须走两条不同的路线吗？ - Kaidul

那么明确一下，您需要找到两条不同的路径吗？如果一条路径上移除了一枚硬币，另一条路径可以通过相同的方格，但不会获得价值吗？ 这些路径是竞争关系（它们想为自己做最好的事情），还是合作关系（追求最佳总价值）？ - Jeff

你在geeksforgeeks给出的解决方案中没有理解的部分是什么，@PrashantBhanarkar？ - Nikhil Pathania

请完整描述问题，而不是链接到一个外部源，说问题“类似于”。 - m69 ''snarky and unwelcoming''

“另一个遍历”的方向重要吗？试着理解j_random_hacker的提示-你可以（当然！）在stackoverflow(/SE)上回答自己的问题。 - greybeard

Answer 1

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

• 首先，我们可以将第二个人的方向反转，使得两个人同时从左上角出发并朝着右下角移动。

• 其次，如果我们假设两个人移动速度相同，则这两个人的状态可以仅用三个参数表示：x1、x2 和 y1。由于我们可以根据第一个人的当前位置（x1 + y1 的和，因为他只能向右或向下移动）轻松计算出他已经移动的步数，所以我们也可以推断出第二个人的当前位置（y2 = x1 + y1 - x2）。请记住，两个人需要在任何给定的时间内走相同的步数才能到达右下方。

• 最后，我们应该注意到一个人不能重复访问一个位置，因为每个人只能向右或向下移动。此外，在任何状态下，两个人所走的步数都是相同的，因此，如果存在被两个人访问的位置，他们将会在同一时间访问该位置（仅当 x1 = x2 时），因此我们可以轻松地计算收集到的硬币数量。

基于这些观察，这个问题可以很容易地转化为 OP 链接中的一个类似问题：

从状态 (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])

- Pham Trung

---

每当两个遍历经过相同的方格时，向下和向右移动或向右和向下移动会导致两个相同的解决方案，因此在这些情况下，您只需要查看三个下一个状态。 - m69 ''snarky and unwelcoming''

你只拿到了一半的赏金？典型。 - m69 ''snarky and unwelcoming''

@PrashantBhanarkar，它为什么不工作？还是你的实现有问题？ - Pham Trung

你可以在你的实现上运行这个案例并查看。 - Prashant Bhanarkar

@BassamMehanni 如果 x2 == x1，那么 y2 == y1。两个人走相同的步数，只能向下或向右走。 - Pham Trung

Answer 2

我不太清楚你需要的两个遍历的确切要求，但对于任何给定的遍历，我建议使用Dijkstra算法，但构建它时，将决定因素从两个节点之间的长度/权重改为网格方格的值。还很重要的是，要确保它检查具有最大值而不是最小值的路径。

采用这种方法应该可以使得如果有多种方法到达一个方格（大多数情况下都会有），算法将忽略除积累了最大值的路径以外的所有路径，从而减少需要检查的路径数量。

例如：

输入：

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.

第二步： P1和P2都可以走向(2,1)的下一步。在蛮力法中，你会让两条路径继续穿过整个图形，但是在这种方法中，我们发现P2比P1更优，所以没有必要继续使用P1，从那个方格开始只需继续使用P2即可。

- Jeff

---

怎么做呢？这不是贪心算法，你要检查所有路径，直到找到一个有多种方法到达的点。当你找到至少两条可能的路径相遇时，你评估所有路径的净值到达该点，并找到最佳路径。只有在那时，你才会忽略任何不能给该点带来最大价值的路径。 - Jeff

如果您对迪科斯彻算法不熟悉，建议您观看此视频（请注意，我建议对其进行编辑）并了解更多信息。https://www.youtube.com/watch?v=WN3Rb9wVYDY - Jeff

Dijkstra算法不能用于计算最大路径。它是NP难问题。 - Pham Trung

如果您将硬币数量视为图中的重量，则不起作用，请考虑从单元格A到单元格B有两条路径，A -> 100 -> 20 -> B和A -> 10 -> 200 -> B，第二条路径将不被考虑，即使它更好。 - Pham Trung

没有仔细看你的示例。你让 P2 从 (0,0) 开始，问题中写着 从右下角到左上角。不确定单次移动是否会改变两个坐标 - 很遗憾，与 GeeksforGeeks 不同的是，这个问题对允许的移动方式没有明确说明。 - greybeard