一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 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.每列求路径可能性
假设是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;
}