我们给出了一个加权的N*N网格W。两个机器人r1、r2分别从左上角和右上角开始。R1必须到达右下角，R2必须到达左下角。以下是有效的动作。
- R1向下移动一个正方形，R2向左移动一个方形
- R1向右移动一个正方形，R2向下移动一个方形
他们必须以这样一种方式移动，即他们访问的正方形(包括起始正方形和结束正方形(的权重之和最大化。
例如，如果网格为：
6 0 3 1 7 4 2 4 3 3 2 8 13 10 1 4在本例中，如果R1遵循*标记的路径，R2遵循标记的路径通过^，如下所示，他们的总分为56。
6* 0 3^ -1^ 7* 4*^ 2^ 4 -3 3*^ -2* 8* 13^ 10^ -1 -4*可以验证的是，这是该网格可以实现的最佳组合分数。
我们不能通过递归来解决这个问题，因为N<=2500，时间限制为2秒
如果问题只有一个机器人，我们可以通过动态编程来解决这个问题。
我试着用类似的方法来解决这个问题；
我们有两个额外的N*N网格G1、G2，
for i from 1 to N:
for j from 1 to N and K from N down to 1:
if (G1[i-1][j] + G2[i][k+1]) > (G1[i][j-1] + G2[i-1][k]):
G1[i][j] = G1[i-1][j] + W[i][j]
G2[i][k] = G2[i][k+1] + W[i][k]
else:
G1[i][j] = G1[i][j-1] + W[i][j]
G2[i][k] = G2[i-1][k] + W[i][k]
return G1[N][N] + G2[N][1]
但这给出了一个错误的答案。我不明白我的算法出了什么问题，因为对于每个正方形，它都在计算最大加权路径。
有人能告诉我我的方法出了什么问题吗？我该如何纠正才能得到正确的答案？
这是一个图问题，图是G=(V,E)，其中：
- V=平方x平方(所有平方的笛卡尔乘积(
(您可能想排除(x1，y1(=(x2，y2(的点，这很容易做到( - E={转弯时所有可能的移动方式}=(或形式上(=
{(((x1，y1(，(x2，y2((，((x1-1，y1
现在，一旦我们有了图-我们可以看到它实际上是一个DAG-这是一件好事，因为对于一般情况的图-最长路径问题是NP难问题，但对于DAG不是。
现在，给定一个DAG G，我们想找到从((0,0),(n,n))到((n,n),(0,0))的最长路径，可以使用以下方法来完成：
为简便起见，定义weight((x1,y1),(x2,y2)) = weight(x1,y1) + weight(x2,y2):
算法：
- 在图上使用拓扑排序
- Init D((n，n(，(0,0((=权重(
- 根据降序对图进行迭代，并对每个顶点
v执行以下操作：
D(v(＝max{D(u(|对于如上所述的E中的每个(v，u(}+权重(v(
当你完成D((0,0(，(n，n((将有最佳结果。
我可以在第二个有效场景中看到一个拼写错误
有效的第二种情况应该是
R1 向右移动一个正方形，R2向下移动一个正方形
但以形式给出
R2 向右移动一个正方形，R2向下移动一个方形