我正在尝试解决类似于GeeksforGeeks的问题，但不同的是：
给定一个矩形二维网格，每个单元格中都有一些硬币值，任务是从左上角和右下角开始向右或向下，从右下角到左上角向左或向上，最大化拾取的硬币组合数量。每个单元格中的硬币只能拾取一次。
链接中的解决方案是同时开始两个遍历，但这在这里行不通。
我应该如何解决这个问题？暴力破解的方法是枚举所有路径，并选择两条路径，最大化选择的硬币总数，但这对大输入不起作用。
我们可以通过三个观察来解决这个问题：
>
首先，我们可以反转第二个人的方向，而不是从两个不同的点开始，所以问题变成两个人从左上角开始，同时向右下角移动。
其次，如果假设两个人的移动速度相同，那么这两个人的状态只能用三个参数来表示：x1、x2和y1。由于我们可以根据第一个人当前的位置轻松计算出他移动的次数（sumx1 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])
我不清楚你需要的2次遍历的确切要求，但对于任何给定的遍历，这里都是我的建议。使用Dijkstra的算法，但要构建它，而不是让决定因素是2个节点之间连接的长度/权重，使其成为网格正方形的值。确保它检查具有最大值而不是最小值的路径也很重要。
采用这种方法应该使得如果有不止一种方法可以到达一个正方形（大多数时候会有），算法将忽略除累积最大值的路径之外的所有路径，从而减少需要检查的路径数量。
前：
输入：
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。
