一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
文章图片
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
解决方法1:递归遍历
通过递归，列出所有可能性,递归停止条件为机器人走到边界或走到终点,如果是终点,total+1
void move(int curX,int curY,int m, int n,int *total) {
if (curX < n - 1) {
move(curX + 1, curY, m, n,total);
}
if (curY < m - 1) {
move(curX, curY + 1, m, n,total);
}
if (curX == n - 1 && curY == m - 1) {
*total = *total + 1;
}
}int uniquePaths(int m, int n) {
int total = 0;
move(0, 0, m, n,&total);
printf("%d\n", total);
return total;
}解决方法2.每列求路径可能性
【62. 不同路径】假设是m行,n列
求不同路径的可能性，可以转换为倒数第二列的每一个点的可能性之和，因为每一个点，只能从上方点或者左方点到达，那么，求该点的路径可能性，即可转换为它上方点的路径可能性与它左边点的路径可能性之和
文章图片
int uniquePaths(int m, int n) {
int* p = (int*)malloc(sizeof(int) * m);
for (int j = 0;
j < m;
j++) {
p[j] = j == 0 ? 1 : 0;
}
int i = 0;
while (i < n - 1) {
for (int j = 0;
j < m;
j++) {
if (j == 0) {
p[j] = 1;
}
else {
p[j] = p[j - 1] + p[j];
}
}
i++;
}
int total = 0;
for (int j = 0;
j < m;
j++) {
total += p[j];
}
printf("%d\n", total);
return total;
}
