leetcode_unique_paths_ii

发表于

难度：Medium

解题思路：使用动态规划。如果没有阻碍ret[i][j] = ret[i-1][j]+ret[i][j-1]，否则ret[i][j]=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> ret(m,vector<int>(n,0));
        ret[0][0] = (obstacleGrid[0][0] == 1)?0:1;
        for(int i = 1; i < n; i++)
            ret[0][i] = (obstacleGrid[0][i]==1)?0:ret[0][i-1];
        for(int i = 1; i < m; i++) 
            ret[i][0] = (obstacleGrid[i][0]==1)?0:ret[i-1][0];
        
        for(int i = 1; i < m; i++)
        {
            for(int j = 1;j < n; j++)
            {
                // cout<<ret[i-1][j]<<" "<<ret[i][j-1]<<endl;
                int rst = ret[i-1][j] + ret[i][j-1];
                ret[i][j] = (obstacleGrid[i][j]==1)?0:rst;
            }
        }
        return ret[m-1][n-1];
    }
};

运行结果：3ms，超过24.08%