我的思路：
1、一个机器人在矩阵的(0,0)点处，到达(i,j)处，只能往下或者右走，有多少种路径？
2、这里由于在每个点只能往下或者往右，只有两种可能，所以走过的点的数量是确定的，而且往每个方向的数目也是确定的，利用组合公式C(n,m) = n! / (m! * (n - m)!。
代码如下：
int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0)
return 0;
int up = m + n - 2;
int down_min = m < n ? (m - 1) : (n - 1);
int down_max = m > n ? (m - 1) : (n - 1);
long long int ans_up = 1, ans_down = 1;
for (int i = down_max + 1; i <= m + n - 2; i++)
ans_up *= i;
for (int i = 1; i <= down_min; i++)
ans_down *= i;
return ans_up / ans_down;
}
其他思路：
1、这个可以用递推来思考，到达最后一个点 f[i][j] 的时候，只有两种情况，来自上方或者左边的点。所以有公式 f[i][j] = f[i - 1][j] + f[i][j - 1]。
2、初始化第一行第一列的值为1。开始循环求出每个点的值。
我的思路：
1、这题运用和上题递推的思路就可以了，只要把初始值设定好之后就用循环生成结果。
2、用－1来表示障碍物，因为1要作为结果来表示。
代码如下：
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int size = obstacleGrid.size();
if (size == 0)
return 0;
int len = obstacleGrid[0].size();
vector<vector<int>> ans = obstacleGrid;
int start = ans[0][0];
for (int i = 0; i < len; i++)
if (ans[0][i] == 1) {
for (int j = i; j < len; j++)
ans[0][j] = -1;
break;
}
else
ans[0][i] = 1;
//第一列要从头开始初始化，如果第一个是障碍物，而且只有一列，从第二列开始初始化就会有问题
ans[0][0] = start;
for (int i = 0; i < size; i++)
if (ans[i][0] == 1) {
for (int j = i; j < size; j++)
ans[j][0] = -1;
break;
}
else
ans[i][0] = 1;
for (int i = 1; i < size; i++)
for (int j = 1; j < len; j++)
if (ans[i][j] != 1)
ans[i][j] = (ans[i - 1][j] == -1 ? 0 : ans[i - 1][j]) + (ans[i][j - 1] == -1 ? 0 : ans[i][j - 1]);
else
ans[i][j] = -1;
return ans[size - 1][len - 1] == -1 ? 0 : ans[size - 1][len - 1];
}
优化思路：
1、其实不需要－1来表示有障碍物，我们用原来数组中的数据就可以表示，在结果中走不通的点就设置为0。
优化代码：
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int size = obstacleGrid.size();
if (size == 0)
return 0;
int len = obstacleGrid[0].size();
vector<vector<int>> ans = obstacleGrid;
for (int i = 0; i < len; i++)
if (obstacleGrid[0][i] == 1) { //这里的if else语句可以改称条件判断式，代码长度减小很多
for (int j = i; j < len; j++)
ans[0][j] = 0;
break;
}
else
ans[0][i] = 1;
for (int i = 0; i < size; i++)
if (obstacleGrid[i][0] == 1) { //同上
for (int j = i; j < size; j++)
ans[j][0] = 0;
break;
}
else
ans[i][0] = 1;
for (int i = 1; i < size; i++)
for (int j = 1; j < len; j++)
if (obstacleGrid[i][j] == 0)
ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
else
ans[i][j] = 0;
return ans[size - 1][len - 1];
}