algorithm - 让 2 个机器人在网格中收集最多的重量，从左上角到右下角不重叠

Question

假设你有一个像下面这样的网格（它可以是任何 m 大小的网格）。机器人 1 和 2 只能从 S 向下或向右移动到 X。你如何通过算法使机器人在不重叠的情况下收集最多的重量？机器人每次都必须同时移动（它必须移动，不能只是跳过回合）。我知道他们不会重叠，他们永远不会有相同的 y 值。

小号 1 4 3 3

1 2 4 6 4

2 4 2 1 5

2 1 5 6 1

9 1 2 3 X

我将接受具有最佳时间和空间复杂度的第一个答案。

标签： algorithm

Answer 1

在每一轮，最多有 4 种可能的移动：

• 机器人 1 倒下，机器人 2 倒下
• 机器人 1 向下，机器人 2 向右
• 机器人 1 向右，机器人 2 向下
• 机器人 1 右，机器人 2 右

这是一个用 Java 实现的递归解决方案。对于给定位置，最佳分数是位于该位置的权重之和 + 4 个可能移动中的最佳分数：

public class Robots
{
    private int[][] grid;
    private int size;

    /*
    * Check if both robots occupy a valid position
    */
    private boolean isValid(int x1, int y1, int x2, int y2)
    {
        if(x1==size || y1==size || x2==size || y2==size)
            return false;
        if(x1==x2)
            return false;
        return true;
    }

    private int getMax(int s1, int s2, int s3, int s4)
    {
        int max = s1;
        if(s2>max)
            max = s2;
        if(s3>max)
            max = s3;
        if(s4>max)
            max = s4;
        return max;
    }

    /*
    * Computes the best score possible from a starting position
    */
    private int getBestScore(int x1, int y1, int x2, int y2)
    {
        if(!isValid(x1, y1, x2, y2))
            return 0;
        int s1 = getBestScore(x1+1, y1, x2+1, y2); // robot 1 down, robot 2 down
        int s2 = getBestScore(x1+1, y1, x2, y2+1); // robot 1 down, robot 2 right
        int s3 = getBestScore(x1, y1+1, x2+1, y2); // robot 1 right, robot 2 down
        int s4 = getBestScore(x1, y1+1, x2, y2+1); // robot 1 right, robot 2 right
        return grid[x1][y1] + grid[x2][y2] + getMax(s1, s2, s3, s4);
    }

    public int solve(int[][] grid)
    {
        this.grid = grid;
        size = grid.length;
        return getBestScore(1, 0, 0, 1);
    }

    public static void main(String[] args)
    {
        int[][] grid = {{0,1,4,3,3}, {1,2,4,6,4}, {2,4,2,1,5}, {2,1,5,6,1}, {9,1,2,3,0}};

        Robots robots = new Robots();
        System.out.println("Best score = " + robots.solve(grid));
    }
}

问题中给出的示例的结果是：

Best score = 48