A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
解题报告（包括了类似题63）：63题中有了obstacle使得问题变的复杂，先来看这一题，很容易得到dp数组的递推式 dp[i][p]=dp[i-1][p]+dp[i][p-1];初始化dp[0][0]=1（因为到第一格只有一种方法），得到了这个式子接下去就简单了。代码如下
int uniquePaths(int m, int n) { int dp[m][n]; for(int i=0;i<m;i++) { for(int p=0;p<n;p++) dp[i][p]=1; } for(int i=1;i<m;i++) { for(int p=1;p<n;p++) { dp[i][p]=dp[i-1][p]+dp[i][p-1]; } } return dp[m-1][n-1]; } 接下来重点说63，因为有了不能走的地方，所以在两层遍历时需要讨论，也就是说只有非obstacle得点才能到达（满足上面所讲的递推式），凡是bostacle点都默认为0。这里注意数组的范围，为了可以包括所有情况我们把数组范围都加1，代码如下
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int size1=obstacleGrid.size(); if(size1==0) return 0; int size2=obstacleGrid[0].size(); int dp[size1+1][size2+1]; if(obstacleGrid[0][0]==1||obstacleGrid[size1-1][size2-1]==1) return 0; for(int i=0;i<=size1;i++) { for(int p=0;p<=size2;p++) { dp[i][p]=0; } } for(int i=0;i<size1;i++) { for(int p=0;p<size2;p++) { if(i==0&&p==0) { if(obstacleGrid[i][p]==0) dp[i+1][p+1]=1; } else { if(obstacleGrid[i][p]==0) dp[i+1][p+1]=dp[i+1][p]+dp[i][p+1]; } } } return dp[size1][size2]; } 总结：依旧是递推式的运用，也就是子问题的寻找，要更加熟练。ps（这两道题分别都有更省空间的方法，待有空再看）。
