给定一个2D字符数组，找到从左上角到右下角的所有路径

Question

给定一个2D字符数组，找出从左上角到右下角的所有可能路径。我有下面的递归解。有人能解释一下如何找到它的复杂性吗?还有，是否有更优的解决方案?我对动态规划不太熟悉，但我认为可以用它来解决这个问题。

    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 right的所有排列。例如，一个4x3的网格将是:

ddrrr
drdrr
drrdr
...
rrrdd

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

Answer 2

我假设你所说的"all possible paths"是指只向左和向下移动，对吗?你的代码似乎就是这么说的。同样重要的是:你是在努力寻找路径，还是只是数它们?

你几乎在每次迭代中都有两次分支，所以我说这是2^n。但是你的答案的大小也是2^n相对于网格的大小

这是你应该如何考虑优化:想象在网格中间有一个任意的正方形。它有一定数量的路径从到，也有一定数量的路径从到。目前，如果你接近一个你之前已经接近过的正方形，你会再次计算出该正方形的所有可能的出口路径。相反，对于每个正方形，一旦计算出它的出口路径，就应该将与该正方形相关的所有路径存储在内存中，以便下一次入口路径找到通往该正方形的路径时，不需要再次递归—只需循环遍历所有出口路径并将当前入口路径附加到它们上。

见:http://en.wikipedia.org/wiki/Memoization

Answer 3

1)你的解决方案只搜索向左和向下移动的路径，因为如果允许任何方向和任何循环，可能有无限多条路径，我认为这是对的。

2)时间复杂度:似乎每条路径的每个节点只生成一次操作总数与路径总数乘以路径长度成正比。所有的路径都有相同的长度(M + N)，我们也可以构造路径数的递归公式:

K(M, N) = K(M - 1, N) + K(M, N - 1)

K(*， *) = K(*， 1) = 1

你可能注意到它与二项式系数的递归公式非常相似所以我们可以得出结论:

K(M, N) ~ C(M + N, N)

更准确:

K (M, N) = C (M + N - 2 N - 1) = C (M + N - 2 M - 1);K(0,0) = 0;

你可以检查这个方程是如何将路径数的递归公式转换为二项式系数的递归公式，并且它可能更容易理解这些数字是如何排列在帕斯卡树上的。因此我们可以得出时间复杂度为O(C(M + N, N) * (M + N))

3)显然，你不能渐进地更快地生成所有路径，因为结果的大小具有相同的复杂性，但如果你不会再次生成所有子路径，当你通过相同的字符时，你可能会达到更好的性能，它可能不容易进行递归，但你可以通过对角线从右下角字符开始循环，并将生成的子路径传递给顶部相邻字符，并将一个副本传递给左侧相邻字符。但正如我所说，它不会足够好，因为复制可能比生成快，但在这种情况下不是渐进的。