algorithm - 给定一个二维字符数组，找到从左上角到右下角的所有路径

Question

给定一个二维字符数组，找到从左上角到右下角的所有可能路径。我有以下递归解决方案。有人可以解释如何找到它的复杂性吗？另外，有没有更优的解决方案？我不太熟悉动态规划，但我认为它可以以某种方式用来解决这个问题。

    public ArrayList<ArrayList<Character>> getPaths(char [][]grid){
        return getPaths(grid, 0, 0, new ArrayList<Character>());
    }

    public ArrayList<ArrayList<Character>> getPaths(char [][]grid, int x, int y, ArrayList<Character> path){
        ArrayList<ArrayList<Character>> allPaths = new ArrayList<ArrayList<Character>>();
        path.add(grid[x][y]);

        ArrayList<Character> path1 = new ArrayList<Character>(path);
        ArrayList<Character> path2 = new ArrayList<Character>(path);
        ArrayList<ArrayList<Character>> val1, val2;
        if(x == grid.length-1 && y == grid[0].length-1){
            allPaths.add(path);
        }
        else{
            if(x < grid.length-1){
                val1 = getPaths(grid, x+1, y, path1);
                for(ArrayList<Character> v1: val1)
                    allPaths.add(v1);
            }
            if(y < grid[0].length-1){
                val2 = getPaths(grid, x, y+1, path2);
                for(ArrayList<Character> v2: val2)
                    allPaths.add(v2);
            }
        }  
        return allPaths;
    }

Answer 1

如果您允许的移动只是向下或向右，另一种思考方式可能是 y-1 down 和 x 的所有排列-1 正确的。例如，4x3 网格将是:

ddrrr
drdrr
drrdr
...
rrrdd

在那种情况下，如果您愿意，而不是递归，您可以使用任意数量的算法来生成“下一个字典排列”(在这种情况下，字符串也可以转换为二进制)来生成路径映射。要生成实际路径，您将从 (0,0) 开始并根据字符是指示向下还是向右更新 x 和 y。