大网格中的机器人说明

Question

我已经对该问题进行了一些研究，但找不到任何解释它的时间复杂性的方法。

破解编码访谈第6版中存在一个问题：

网格中的机器人：想象一个机器人坐在具有r行和c列的网格的左上角。机器人只能在左右两个方向上移动，但是某些单元格处于“禁区”，因此机器人无法踩踏它们。设计算法以从左上角到右下角找到机器人的路径

这是作者的解决方案，她解释说这个问题有O（2 ^（r + c））并使用记忆成本O（r * c）（其中r是行数，c是列数）] >

“此解决方案为O（2 ^（r + c）），因为每条路径都有r + c步，我们可以在每个步中做出两个选择”

ArrayList<Point> getPath(boolean[][] maze) {
2 if (maze == null || maze.length == 0) return null;
3 ArrayList<Point> path = new ArrayList<Point>()j
4 if (getPath(maze, maze.length - 1, maze[0].length - 1, path)) {
5 return path;
6 }
7 return null;
8 }
9
10 boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
11 / * If out of bounds or not available, return. */
12 if (col < 0 || row < 0 || !maze[row][col]) {
13 return false;
14 }
15
16 boolean isAtOrigin = (row == 0) && (col == 0);
17
18 /* If there's a path from the start to here, add my location. */
19 if (isAtOrigin || getPath(maze, row, col - 1, path) ||
2B getPath(maze, row - 1, col, path)) {
21 Point p = new Point(row, col);
22 path.add(p);
23 return true;
24 }
25
26 return false;
27 }
并且在添加哈希图以缓存先前调用的失败点时，为什么仅花费O（r * c）？

boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path,
12 HashSet<Point> failedPoints) {
13 /* If out of bounds or not available, return. */
14 if (col < 0 || row < 0 || !maze[row][col]) {
15 return false;
16 }
17
18 Point p = new Point(row, col);
19
20 /* If we've already visited this cell, return. */
21 if (failedPoints.contains(p)) {
22 return false;
23 }
24
25 boolean isAtOrigin = (row == 0) && (col == 0);
26
27 /* If there's a path from start to my current location, add my location. */
28 if (isAtOrigin || getpath(maze, row, col - 1, path, failedPoints) ||
29 getPath(maze, row - 1, col, path, failedPoints) {
30 path.add(p);
31 return true;
32 }
33
34 failedPoints.add(p); // Cache result
35 return false;
36 }
Stackoverflow上的几篇文章解释了从起始位置到结束位置有多少种方法（r + c）！/（r！c！），但我不明白为什么Kayle解释上述解决方案是O（2 ^（r + c））并使用记忆成本O（r * c）。有人可以为我清楚地解释吗？如果您能提供帮助，我将不胜感激。

我已经对该问题进行了一些研究，但找不到任何解释它的时间复杂性的信息。在破解第6版编码访谈时，存在一个问题：网格中的机器人：想象一个...

Answer 1

实际上，此类问题需要图表和GIF来以完美的方式解释该算法。但是，我会尽力用语言来解释它。