最大的赏金来自两个穿过矩形网格的裸片 [英] Maximum bounty from two pathes through a rectangular grid

问题描述

我正在努力解决类似于在GeeksforGeeks的问题，但不同：

给定一个矩形的2-d网格，每个单元格中存在一些硬币值，任务是从左上角和右下角开始角落向右或向右，从右下到左上左右，最大化拾取的硬币的总和。每个单元格中的硬币只能被选择一次。

链接中的解决方案是同时开始遍历，但这不会在这里工作。

我该如何解决？这种做法的强力方式是枚举所有路径，并选择两个最大化所选硬币总和的路径，但这不会为大型输入工作。

I am trying to solve problem similar to this problem at GeeksforGeeks, yet different:
Given a rectangular 2-d grid with some coin value present in each cell, the task is to start from the top-left and bottom-right corner going right or down, and from bottom-right to top-left going left or up, maximizing the combined amount of coin picked. Coin in each cell can be picked only once.
The solution in the link is to start both traversal simultaneously but that's not going to work here.
How should I solve this? The brute force way of doing this would be enumerating all paths and picking two paths that maximizes the sum of coins picked but that's not going to work for large input.

推荐答案

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

We can solve this problem by making three observations:

• 首先，而不是从两开始不同的点，我们可以扭转第二个人的方向，所以问题成为两个人从左上角开始，同时向右下角移动。

• First, rather than starting at two different points, we can reverse the direction of the second person, so the problem become two people start at the top left corner and move toward bottom right corner simultaneously.

第二，如果我们假设两个人以相同的速度移动，这两个状态只能由三个参数表示： x1，x2和y1 。由于我们可以根据他目前的位置（总和 x1 + y1 ，因为他只能向右或向下移动）轻松计算第一个人所做的移动次数，所以，我们还可以弄清楚第二个人的当前位置（ y2 = x1 + y1 - x2 ）。请记住，两者都需要相同数量的步骤才能到达右下角，所以在任何给定的时间内，两者都将具有相同的移动次数。

Second, if we make an assumption that, two persons will make their move at the same speed, the state of these two can be represented by only three parameters: x1, x2 and y1. As we can easily calculate the number of move the first person had made based on his current location (sum x1 + y1, as he can only move right or down), so, we can also figure out the current location of second person (y2 = x1 + y1 - x2). Keep in mind that, both need to make same number of step to reach the bottom right, so both will have same number of move in any given time.

最后，我们应该注意到，一个人不能访问一个以上的位置，因为每个人可以采取的唯一方向是对或下。此外，在任何状态下，每个人的移动次数相等，所以如果存在两个人访问的位置，他们将同时访问这个位置（只有当 x1 = x2 ），因此，我们可以轻松计算收集的硬币数量。

Lastly, We should notice that, a person cannot visit a location more than one, as the only directions each can take are right or down. Further more, in any state, the number of move each person made are equaled, so, if there exists location(s) visited by both persons, they will visit this location at the same time (and only when x1 = x2), thus, we can easily count the number of coins collected.

从这些观察结果可以很容易地减少OP的链接中的问题类似的问题：

From these observations, it can be easily reduced to a similar problem to the problem in OP's link:

从状态（x1，x2， y1），因为每个人只能向右或向下移动，我们将有以下下一个状态：

Starting from state (x1, x2, y1), as each person can only move right or down, we will have following next states:

 (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.

所以，我们有动态编程公式：

So, we have our dynamic programming formula:

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])

这篇关于最大的赏金来自两个穿过矩形网格的裸片的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！