假设您有一个下面这样的网格(它可以是任何m大小的网格(。机器人1和2只能从S向下或向右移动到X。如何通过算法使机器人在不重叠的情况下收集最多的重量？机器人每次都必须在同一时间移动(它必须移动，不能跳过转弯(。我知道，如果它们不重叠，就不可能有相同的y值。
S 1 4 3 3
1 2 4 6 4
2 4 2 1 5
2 1 5 6 1
9 1 2 3 X
我将以最好的时间接受第一个答案；空间复杂性。
每个回合，最多有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
在O(m^3(时间和O(m^2(空间中求解是可能的，类似于一个机器人在O(m ^2(时间和O(m(空间中的求解。
对于一个机器人，你有一个k步(对角线(后可能值的数组，然后你通过考虑可能的两个移动来构建k+1步后的可能值。
对于两个机器人，它不是k步后的矩阵，一个机器人的位置在一个轴上，另一个机器人在另一轴上，这给出了空间要求，每个矩阵元素最多基于前一步中的2x2，到目的地有O(m(步，所以它应该是O(m^3(时间。
我在O(n^3(时间|O(n^2(空间中解决了这个问题。
解释是将有最大n个转弯。你只需要存储上一个转弯就可以计算下一个转弯。在每一轮中，可能有最多n^2个有效位置的组合。由于您必须经历n次n^2个组合，因此运行时间为n^3。