Pra*_*kar 4 algorithm path-finding graph-algorithm
我试图解决类似于GeeksforGeeks这个问题的问题,但是不同的是:
给定一个矩形的2-d网格,每个单元格中都有一些硬币值,任务是从左上角和右下角开始向右或者向下,从左下角到左上角向左或向上,最大化拾取的硬币总量.每个单元格中的硬币只能被挑选一次.
链接中的解决方案是同时启动两个遍历,但这不会在这里工作.
我该怎么解决这个问题？执行此操作的蛮力方式是枚举所有路径并选择两条路径,以最大化所拾取的硬币总和,但这对于大输入不起作用.
我们可以通过三个观察来解决这个问题:
首先,不是从两个不同的点开始,我们可以反转第二个人的方向,因此问题变成两个人从左上角开始并同时向右下角移动.
其次,如果我们假设两个人将以相同的速度移动,那么这两个人的状态只能由三个参数表示:x1, x2 and 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])