上周他们弄了一道阿里的面试算法题，没有正确答案，而且题目比较复杂，就不写了，这周两道题是同一种类型的题，就一起做了，难度级别都是'Medium'，使用语言都是'C'。
题目：在一个m*n的格子里，从左上角走到右下角有多少种走法(只能往右和往下走)
思路：这就标准的动态规划题，关于动态规划，可以看看这篇文章,这个题的算法其实就是将第一行和第一列填1，然后左边格子与上边格子的和就是当前格子的数，填到右下角的数就是结果。具体看代码：
int uniquePaths(int m, int n) {
//定义一个数组
int res[n];
//左边第一个数为1
res[0] = 1;
for(int i=0;i<m;i++)
for(int j=1;j<n;j++)
//初始化赋值
if (i == 0) res[j] = 0;
//左边res[j-1]和上边的数res[j]求和
res[j] += res[j-1];
//返回右下角的结果
return res[n-1];
}
接着直接看第二道：
题目：给你一个m*n的格子，格子中有障碍物，我们记为1，遇到障碍物就无法通行了，然后同样的是让你从左上角走到右下角，求有多少种走法。
思路：这个题思路和上面一样，只是遇到障碍物将结果置为0即可，具体看代码：
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {
//如果左上角（起点）或者右下角（重点）有障碍物，直接返回0种走法
if (obstacleGrid[0][0] || obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize-1]) return 0;
//定义容器
int res[obstacleGridColSize];
//左边第一个数为1
res[0] = 1;
for(int i = 0;i < obstacleGridRowSize; i++) {
for(int j = 0;j < obstacleGridColSize; j++) {
//初始化赋值
if (i == 0 && j != 0) res[j] = 0;
//如果是障碍物，记为0
if(obstacleGrid[i][j]==1) res[j]=0;
//否则如果不是第一列，则加上左边和上边的数
else if(j) res[j] += res[j-1];
}
}
return res[obstacleGridColSize-1];
}
效率一般，但cpp用这种解法效率就是最好，这种类型的题还有很多种解法，有兴趣的小伙伴可以再尝试用其他的方法解，递归容易超时，就不要用递归了。
