在 NxN 网格中查找所有路径的算法

Question

想象一个机器人坐在 NxN 网格的左上角。机器人只能在两个方向上移动：向右和向下。机器人有多少条可能的路径？

我可以在谷歌上找到这个问题的解决方案，但我对解释不是很清楚。我试图清楚地理解如何解决这个问题并用 Java 实现的逻辑。任何帮助表示赞赏。

更新：这是一个面试问题。现在，我正在尝试到达右下角并打印可能的路径。

原文由 Periastron 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在您的问题中，我看不到任何障碍的迹象，因此我们可以假设没有障碍。

请注意，对于 n+1 x n+1 网格，机器人需要精确走 2n 步才能到达右下角。因此，它最多只能移动 2n 步。

让我们从一个更简单的案例开始： [找到右下角的所有路径]

机器人可以精确地 choose(n,2n) = (2n)!/(n!*n!) 路径：它只需要选择 2n 中的哪一个，剩下的就是正确的 n 其中）。

要生成可能的路径： 只需生成大小为 2n 的所有 二进制向量，其中 n 为 1。 1 表示向右移动，0 表示向下移动。

现在，让我们将其扩展到所有路径：

首先选择路径的长度。为此，遍历所有可能性： 0 <= i <= 2n ，其中 i 是路径的长度。在此路径中有 max(0,i-n) <= j <= min(i,n) 正确的步骤。

要生成所有可能性，请实现以下伪代码：

 for each i in [0,2n]:
  for each j in [max(0,i-n),min(i,n)]:
    print all binary vectors of size i with exactly j bits set to 1

注 1： 打印所有大小为 i 且 j 位设置为 1 的二进制向量可能计算量大。这是意料之中的，因为解决方案的数量呈指数级增长。

注 2： 对于案例 i=2n ，你得到 j in [n,n] ，正如预期的那样（上面描述的更简单的案例）。

原文由 amit 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

public static int computePaths(int n){
    return recursive(n, 1, 1);
}

public static int recursive(int n, int i, int j){
    if( i == n || j == n){
        //reach either border, only one path
        return 1;
    }
    return recursive(n, i + 1, j) + recursive(n, i, j + 1);
}

要找到所有可能的路径：

仍然使用递归方法。路径变量在开始时被赋值为“”，然后将访问的每个点添加到“路径”中。当到达(n,n)点时形成一条可能的路径，然后将其添加到列表中。

每条路径都表示为一个字符串，例如“(1,1) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4)”。所有可能的路径都存储在一个字符串列表中。

 public static List<String> robotPaths(int n){
    List<String> pathList = new ArrayList<String>();
    getPaths(n, 1,1, "", pathList);
    return pathList;
}
public static void getPaths(int n, int i, int j, String path, List<String> pathList){
    path += String.format(" (%d,%d)", i , j);
    if( i ==n && j == n){ //reach the (n,n) point
        pathList.add(path);
    }else if( i > n || j > n){//wrong way
        return;
    }else {
        getPaths(n, i +1, j , path, pathList);
        getPaths(n, i , j +1, path, pathList);
    }
}

原文由 Ethan 发布，翻译遵循 CC BY-SA 3.0 许可协议