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

Question

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

我可以在Google上找到解决这个问题的方法,但我对解释并不十分清楚.我试图清楚地理解如何解决这个问题并在Java中实现的逻辑.任何帮助表示赞赏.

更新:这是一个面试问题.现在,我正试图到达右下角并打印可能的路径.

Answer 1

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);
    }
}

Answer 2

我认为你的问题没有障碍的迹象,所以我认为没有障碍.

请注意,机器人需要采取恰好2n步骤才能到达右下角.因此,它不能再2n动作了.

让我们从这个私人案例开始: [找到右下角的所有路径]

机器人可以精确地制作路径:它只需要选择这些移动中的哪一个是正确的,其余的都是向下的[并且正是那些] 为了生成可能的路径:只生成大小正好为1的所有二进制向量.1表示右移,0表示向下移动.choose(n,2n)= (2n)!/(n!*n!)2nn
2nn

现在,让我们将它扩展到所有路径:
首先需要选择路径的长度.只是迭代所有可能性: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]看到[我们上面描述的私人案例].