c++ - 使用动态编程计算网格中的路径数量？

坐在nxn网格左上角的机器人。机器人只能向两个方向移动：向右和向下，其中一些细胞死亡，即机器人无法进入该细胞。机器人有多少可能的路径？
这可以用回溯来解决，但是时间复杂度太高。我用回溯法解决了这个问题，但在更坏的情况下需要O（2 ^ n）。

bool exist(bool a[][], int i, int j,int N){
        return i>=0 && j >=0 && i < N && j < N;
    }
    int search(bool  a[][], int i, int j,int N){
        if(!exist(a,i,j,N) || a[i][j] == 1)
            return 0; // no path here.
        if(i == N-1 && j == N - 1){
            return 1; // 1 path here.
        }
        a[i][j] = 1; // mark that we have seen this spot here
        int paths = 0; // introduce a counter...
        paths += search(a, i,j+1,N); // add the additional paths as we find them
        paths += search(a, i+1,j,N);
        a[i][j] = 0;
        return paths; // return the number of paths available from this point.
    }

这里有1个单元代表死单元。有没有办法通过使用DFS或动态编程E.T.C来减少时间复杂度？

最佳答案

给定一个NxN grid，让ways[i][j] = number of possible paths from grid[0][0] to grid[i][j]
初始化grid[0][0] = 1
如果grid[i][j] is dead，ways[i][j] = 0
否则（但小心边缘）
例如：

grid:(1 means dead)   ways:

0 0 1 0 0             1 1 0 0 0
0 0 0 0 0             1 2 2 2 2
0 1 0 0 1             1 0 2 4 0
1 0 0 0 0             0 0 2 6 6
0 0 0 0 0             0 0 2 8 14

我认为复杂性是ways[i][j] = ways[i-1][j] + ways[i][j-1]自从O(n^2)网格。