使用动态规划计算网格中的路径数？

Question

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来降低时间复杂性吗？

Answer 1

让我们假设下面的3x3网格，其中网格中的1表示障碍物

[0,0,0]
[0,1,0]
[0,0,0]

本例中唯一路径的数目为2。我们可以使用动态编程的方法来降低时间复杂度，找到唯一的路径，下面是C++中的代码

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
       int m = obstacleGrid.size();
       int n = obstacleGrid[0].size();

    vector<vector<int> > arr(m,vector<int>(n,0));

    if (obstacleGrid[0][0]==1){return 0;}
    arr[0][0]=1;
    for (int i=1;i<m;i++){
        if (obstacleGrid[i][0]!=1){
            arr[i][0] = arr[i-1][0];
        }
    }
    for (int i=1;i<n;i++){
        if (obstacleGrid[0][i]!=1){
            arr[0][i] = arr[0][i-1];
        }
    }
    for (int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if (obstacleGrid[i][j]!=1){
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
    }   
    return arr[m-1][n-1];
}