我正在尝试解决与此类似的问题 problem at GeeksforGeeks , 但不同:
给定一个矩形二维网格，每个单元格中都有一些硬币值，任务是从左上角和右下角开始向右或向下，然后从右下角到左上角向左或向上，最大化拾取硬币的总数量。每个单元格中的硬币只能被拾取一次。
链接中的解决方案是同时开始遍历，但这在这里行不通。
我应该如何解决这个问题？这样做的蛮力方法是枚举所有路径并选择两条路径，使所选择的硬币总和最大化，但这不适用于大输入。
最佳答案
我们可以通过三个观察来解决这个问题:
首先，我们可以反转第二个人的方向而不是从两个不同的点开始，所以问题变成了两个人从左上角开始并同时向右下角移动。
其次，如果我们假设，两个人将以相同的速度移动，那么这两个人的状态只能由三个参数表示:
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])
关于algorithm - 通过矩形网格的两条路径的最大赏金，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40128689/