本文共 1357 字，大约阅读时间需要 4 分钟。

class Solution {//DP//if a[i][j] is a obstacle, then f[i][j]=0public:	 int uniquePathsWithObstacles(vector
   
    
      > &obstacleGrid) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		 int m = obstacleGrid.size();		 if(0 == m) return 0;		 int n = obstacleGrid[0].size();		vector
     
      
       > f(m+1, vector
       
        (n+1, 0));		if(obstacleGrid[0][0] != 1)			f[1][1] = 1;		for (int i = 1; i <= m; ++i)		{			for (int j = 1; j <= n; ++j)			{				if(i == 1 && j == 1) continue;				if(0 == obstacleGrid[i-1][j-1])//empty 					f[i][j] = f[i-1][j]+f[i][j-1];			}		}		return f[m][n];	}};
       
      
     
    
   

second time

class Solution {public:    int uniquePathsWithObstacles(vector
   
    
      > &obstacleGrid) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int m = obstacleGrid.size();        if(m == 0) return 0;        int n = obstacleGrid[0].size();                vector
     
      
        > f(m+1, vector
       
        (n+1, 0));        for(int i = 1; i <= m; ++i)        {            for(int j = 1; j <= n; ++j)            {                if(obstacleGrid[i-1][j-1] == 1) continue;                                if(i == 1 && j == 1) f[i][j] = 1;                else f[i][j] = f[i-1][j]+f[i][j-1];            }        }        return f[m][n];    }};
       
      
     
    
   

转载地址：http://ihxti.baihongyu.com/