分析：

思路首先：令从（1。1）到（m,n）的最大走法数为dp[m,n]
不论什么一个点都是从上面走下来和从右边走过来两种可能的和
显然dp[m,n]=dp[m-1,n]+dp[m,n-1]
最简单的动态规划问题...........时间复杂度O(M*N)。空间复杂度O(M*N)

class Solution {  
public:  
    int uniquePaths(int m, int n) {  
        vector< vector<int> >  result(m+1);   
        for(int i=0;i <=m ;i++)   
                result[i].resize(n+1);//设置数组的大小m+1行，n+1列   
        for(int i=1;i<=n;i++)  
            result[1][i]=1;  
        for(int i=1;i<=m;i++)  
            result[i][1]=1;  
        for(int i=2;i<=m;i++)  
            for(int j=2;j<=n;j++)  
                result[i][j]=result[i-1][j]+result[i][j-1];  
        return result[m][n];  
    }  
};  

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

思路首先：
此题与原问题相较，变得是什么？
1。此障碍物以下和右边将不在获得来自于此的数量,也能够理解为贡献为0
2。有障碍的地方也将无法到达（这一条開始时没想到。总感觉leetcode题目意思不愿意说得直接明了）。也就是说此点的可到达路劲数直接为0

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector< vector<int> >  result(m+1);   
        for(int i=0;i <=m ;i++)   
            result[i].resize(n+1);//设置数组的大小m+1行。n+1列   
        //初始化一定要正确。否则错无赦    
        result[1][1]= obstacleGrid[0][0]==1?
 0:1;    
        for(int i=2;i<=n;i++)  
            result[1][i]=obstacleGrid[0][i-1]==1?0:result[1][i-1];//由上一次来推到  
        for(int i=2;i<=m;i++)  
            result[i][1]=obstacleGrid[i-1][0]==1?0:result[i-1][1];  
            
        for(int i=2;i<=m;i++)  
            for(int j=2;j<=n;j++)  
                result[i][j]=obstacleGrid[i-1][j-1]==1?0:result[i-1][j]+result[i][j-1];  //一旦当前有石头就无法到达，直接置零
            
        return result[m][n];
    }
};

联动另外一个问题：

分析：

非常显然的动态规划问题。

令从原点（1，1）到目的点（m,n）的最小路劲和为result[m,n] 
不论什么一个点的路劲和都是来自二维数组上一行的最小路劲和或者来自右一列的最小路劲和与当前位置的值相加的结果 显然result[m,n]=min(result[m-1,n]+grid[m,n],result[m,n-1]+grid[m,n]) 
注意初始化问题

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row=grid.size();//行
        int col=grid[0].size();
        vector< vector<int> >  result(row);     
        for(int i=0;i <row ;i++)     
            result[i].resize(col,0);//设置数组的大小row行。col列 
        result[0][0]=grid[0][0];//初始化    
        for(int i=1;i<col;i++)//初始化第一行
            result[0][i]=result[0][i-1]+grid[0][i];
        for(int i=1;i<row;i++)//初始化第一列
            result[i][0]=result[i-1][0]+grid[i][0];
        for(int i=1;i<row;i++)//计算中间结果
            for(int j=1;j<col;j++)
                result[i][j]=min(result[i][j-1]+grid[i][j],result[i-1][j]+grid[i][j]);
        return result[row-1][col-1];
    }
};

注：本博文为EbowTang原创。兴许可能继续更新本文。

假设转载，请务必复制本条信息！

原文地址：http://blog.csdn.net/ebowtang/article/details/50485468

原作者博客：http://blog.csdn.net/ebowtang

本博客LeetCode题解索引：http://blog.csdn.net/ebowtang/article/details/50668895