网格中双机器人从左上到右下不重叠收集最大权重算法求解

• 两个机器人同步移动，每次仅向右或向下走1步，因此走k步后任意机器人的坐标满足x + y = k，无需额外存储x坐标，可通过x = k - y推导
• 要求移动过程中y坐标不同，因此我们可以约定y1 < y2，既避免重复计算对称状态，又自动满足不重叠约束
• 终点处两个机器人同时抵达X，权重仅计算1次

这是理论最优的复杂度，因为网格本身为m×m大小，不可能存在低于O(m²)的解法。

状态定义 #

用dp[k][y1][y2]表示走了k步后，第一个机器人y坐标为y1、第二个为y2时的最大权重和。
为优化空间，我们采用滚动数组：仅保留上一步的状态数组prev_dp[y1][y2]和当前步的状态数组curr_dp[y1][y2]，空间复杂度直接压缩到O(m²)。

状态转移 #

每个机器人的上一步状态仅有两种可能：

1. 上一步向下走：y坐标和当前一致，x坐标少1
2. 上一步向右走：y坐标比当前少1，x坐标一致
   因此两个机器人的组合转移共有4种可能，我们取4种转移的最大值，再叠加当前两个格子的权重即可：

curr_dp[y1][y2] = max(
    prev_dp[y1][y2],    // 第一个下、第二个下
    prev_dp[y1][y2-1],  // 第一个下、第二个右
    prev_dp[y1-1][y2],  // 第一个右、第二个下
    prev_dp[y1-1][y2-1] // 第一个右、第二个右
) + grid[x1][y1] + grid[x2][y2]

注：k为最后一步（即两个机器人都抵达X点）时，权重仅加1次grid[m-1][m-1]，避免重复计算。

边界条件 #

初始状态k=0时，两个机器人都在起点S，因此prev_dp[0][0] = grid[0][0]，其余状态初始化为负无穷代表不可达。

计算流程 #

1. 预处理网格：将S和X替换为对应权重，无特殊说明默认设为0
2. 初始化滚动数组prev_dp，所有值设为负无穷，仅prev_dp[0][0]为起点权重
3. 遍历每一步k从1到2m-2（从起点到终点共需走2m-2步）：
   • 初始化curr_dp所有值为负无穷
   • 遍历所有合法的y1、y2，要求y1 < y2，且x1 = k - y1、x2 = k - y2都在网格范围内
   • 枚举4种转移可能，校验转移前的y坐标合法性后，更新当前状态的最大权重和
   • 将prev_dp替换为curr_dp，进入下一轮计算
4. 最终结果为prev_dp[m-1][m-1]

针对给出的5×5网格，用上述算法计算可得最大权重和为47。

内容的提问来源于stack exchange，提问作者coolcool1994