关于c:62-不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的门路？

示例 1：

输出：m = 3, n = 7
输入：28

示例 2：
输出：m = 3, n = 2
输入：3
解释：
从左上角开始，总共有 3 条门路能够达到右下角。

1. 向右 -> 向下 -> 向下
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. 每列求门路可能性

假如是 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;
}