参考文章：代码随想录https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
一、题目
一个机器人位于一个 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 * 10^9^
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths
二、题解
动态规划
机器人从 (0, 0) 位置出发，到 (m – 1, n – 1) 终点。
按照动规五部曲来分析：
- 确定 dp 数组（dp table）以及下标的含义
此题与之前的题目相比，需要用一个二维的 dp 数组
dp[i][j]：表示从（0，0）出发，到（i，j）有 dp[i][j] 条不同的路径。
- 确定递推公式
想要求 dp[i][j]，只能有两个方向来推导出来，即 dp[i – 1][j] 和 dp[i][j – 1]。
此时再回顾一下 dp[i – 1][j] 表示啥，是从 (0, 0) 的位置到 (i – 1, j) 有几条路径，dp[i][j – 1] 同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为 dp[i][j] 只有这两个方向过来。
- dp 数组的初始化
如何初始化呢，首先 dp[i][0] 一定都是 1，因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条，那么 dp[0][j] 也同理。
所以初始化代码为：
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;- 确定遍历顺序
这里要看一下递推公式 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j] 都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导 dp[i][j] 的时候，dp[i – 1][j] 和 dp[i][j – 1] 一定是有数值的。
- 举例推导 dp 数组
以 m = 3，n = 3 为例，dp = [[1, 1, 1], [1, 2, 3], [1, 3, 6]]
最后还可以优化点空间，用一个一维数组（也可以理解是滚动数组）就可以了。
public class T62 {
// 二维dp数组版本
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// 一开始我觉得dp[0][0]初始化为0就行
// 后面力扣一提交后发现官方的测试用例是dp[0][0]=1
// dp[0][0]=0;
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
// 一维dp数组版本
public int uniquePaths2(int m, int n) {
int[] dp = new int[n];
/*for (int j = 0; j < n; j++) {
dp[j] = 1;
}*/
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}数论方法
由于机器人每次只能向下或者向右移动一步，要想从 m x n 网格的左上角到达右下角，必然要向下走 m – 1 步和向右走 n – 1 步，即一共要走 m + n – 2 步。所以这就成了一个组合问题，m + n – 2 个不同的数中随便取 m – 1 个数有几种取法。答案就是 C(m+n-2, m-1)
但是求组合的时候，要防止两个 int 相乘溢出！所以不能把算式的分子都算出来，分母都算出来再做除法。例如如下代码是不行的。
public class T62 {
// 数论方法错误写法
public int uniquePaths3(int m, int n) {
int numerator = 1, denominator = 1;
int count = m - 1;
int t = m + n - 2;
while (count != 0) {
numerator *= t; // 计算分子，此时分子就会溢出
t--;
count--;
}
for (int i = 1; i <= m - 1; i++) denominator *= i; // 计算分母
return numerator / denominator;
}
}需要在计算分子的时候，不断除以分母，代码如下：
public class T62 {
// 数论方法正确写法
public int uniquePaths4(int m, int n) {
long numerator = 1; // 分子
int denominator = m - 1; // 分母
int t = m + n - 2;
for (int count = denominator; count != 0; count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return (int) numerator;
}
}另外由于 C(m, n) = C(m, m-n)，例如 C(5, 2) = C(5, 3)，所以 C(m+n-2, m-1) = C(m+n-2, n-1)，所以可以比较一下 m – 1 和 n – 1，即比较 m 和 n，算小的那个，从而减少算组合数时分子的乘法计算次数
public class T62 {
// 数论方法正确写法
public int uniquePaths4(int m, int n) {
long numerator = 1; // 分子
int denominator = m - 1; // 分母
int t = m + n - 2;
// 优化写法一
if (t - denominator < denominator) denominator = t - denominator;
for (int count = denominator; count != 0; count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return (int) numerator;
}
// 数论方法，优化写法二
public int uniquePaths5(int m, int n) {
long numerator = 1; // 分子
int t = m + n - 2;
int denominator;
if (n < m) {
denominator = n - 1;
} else {
denominator = m - 1; // 分母
}
for (int count = denominator; count != 0; count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return (int) numerator;
}
}