63. Unique Paths II

1、Description

样例

2.思路--动态规划

首先该问题由于限定了移动的方向只能向右或者向下，因此该问题具有最优

子结构的性质。不难得到规划矩阵m，其中m[i][j]表示走到地图中(i,j)的路径数，那么可以得到以下的递推方程。

 

m[i,j] = m[i][j-1] + m[i-1][j]

对于所给的case的递推矩阵如下所示，红色部分为初始化的结果，绿色部分为根据初始化条件递推求解的结果。

递推矩阵

1	1	1
1	0	1
1	1	2

 

3.编程实现(java)

首先需要对规划矩阵m的第0行和第0列进行初始化，能走到的地方m[i][j]=1,不能走到的地方m[i][j]=0。然后采用两层for循环进行求解，算法的时间复杂度为O(n²)，空间复杂度为而外维护的矩阵m也是O(n²)。

以下为java代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length==0)return 0;
        int[][] m = new int[obstacleGrid.length][obstacleGrid[0].length];

        //initial the first col
        for(int i=0;i<obstacleGrid.length;i++){
            if(obstacleGrid[i][0]==1)
                break;
            else
                m[i][0] = 1;
        }
        //initial the first row
        for(int j=0;j<obstacleGrid[0].length;j++){
            if(obstacleGrid[0][j]==1)
                break;
            else
                m[0][j] = 1;
        }
        for(int i=1;i<m.length;i++){
            for(int j=1;j<m[0].length;j++){
                if(obstacleGrid[i][j]!=1){
                    if(m[i-1][j]!=0){
                        m[i][j] += m[i-1][j];
                    } 
                    if(m[i][j-1]!=0){
                        m[i][j] += m[i][j-1];
                    }
                }
            }
        }
        return m[m.length-1][m[0].length-1];
    }
}