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

Question

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

我可以在谷歌上找到这个问题的解决方案，但我对解释不是很清楚。我试图清楚地理解如何解决这个问题并在 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);
    }
}