我正在尝试解决类似于GeeksforGeeks上的这个问题,但有所不同:(参考链接)
给定一个矩形2D网格,每个单元格中都有一定数量的硬币价值。任务是从左上角和右下角开始向右或向下移动,并从右下角到左上角向左或向上移动,最大化收集的硬币总价值。每个单元格中的硬币仅能被收集一次。
该链接中的解决方案是同时开始两个穿越路径,但这种方法在这里不适用。
我应该如何解决此问题? 暴力枚举所有路径并选择两条使得硬币总价值最大的路径可能行不通,因为输入规模很大。
我正在尝试解决类似于GeeksforGeeks上的这个问题,但有所不同:(参考链接)
给定一个矩形2D网格,每个单元格中都有一定数量的硬币价值。任务是从左上角和右下角开始向右或向下移动,并从右下角到左上角向左或向上移动,最大化收集的硬币总价值。每个单元格中的硬币仅能被收集一次。
该链接中的解决方案是同时开始两个穿越路径,但这种方法在这里不适用。
我应该如何解决此问题? 暴力枚举所有路径并选择两条使得硬币总价值最大的路径可能行不通,因为输入规模很大。
我们可以通过以下三个观察来解决这个问题:
首先,我们可以将第二个人的方向反转,使得两个人同时从左上角出发并朝着右下角移动。
其次,如果我们假设两个人移动速度相同,则这两个人的状态可以仅用三个参数表示: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])
x2 == x1
,那么 y2 == y1
。两个人走相同的步数,只能向下或向右走。 - Pham Trung我不太清楚你需要的两个遍历的确切要求,但对于任何给定的遍历,我建议使用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.
P2
从 (0,0)
开始,问题中写着 从右下角到左上角
。不确定单次移动是否会改变两个坐标 - 很遗憾,与 GeeksforGeeks 不同的是,这个问题对允许的移动方式没有明确说明。 - greybeard