7-003-(LeetCode- 62) 不同路径
1. 题目
读题
https://leetcode.cn/problems/unique-paths/
考查点
这道题的考查点主要是**动态规划**的思想，也就是把一个复杂的问题分解成多个子问题，用一个数组或矩阵来存储子问题的解，然后通过状态转移方程来求解最终的问题。¹²⁴
动态规划的难点在于找到合适的状态转移方程，也就是如何从已知的子问题的解推导出更大的子问题的解，直到得到最终问题的解。¹²⁴
这道题还可以用**排列组合**的方法来解决，也就是利用数学公式来计算从左上角到右下角需要走多少步，然后在这些步数中选择向下或向右走的步数，求出所有可能的组合数。²
这种方法的难点在于避免溢出，也就是要注意阶乘运算可能会超过整数范围，需要用更大的数据类型或者优化计算过程。²
2. 解法
思路
这道题的解答思路是这样的：
首先，我们可以用一个二维数组dp[m][n]来存储到达每个格子的路径数，初始条件是dp[0][0] = 1，表示从左上角到左上角只有一种路径。
然后，我们可以遍历每个格子，根据它的位置来更新dp数组的值。有三种情况：
- 如果格子在第一行，那么它只能从左边的格子来，所以dp[i][j] = dp[i][j-1]。
- 如果格子在第一列，那么它只能从上面的格子来，所以dp[i][j] = dp[i-1][j]。
- 如果格子在其他位置，那么它可以从左边或上面的格子来，所以dp[i][j] = dp[i-1][j] + dp[i][j-1]。
最后，我们返回dp[m-1][n-1]，就是右下角的值，也就是从左上角到右下角的路径数。
代码逻辑
代码的逻辑是这样的：
首先，我们创建一个二维数组dp，用来存储到达每个格子的路径数，初始化为1，表示每个格子都至少有一种路径。
然后，我们用两个嵌套的for循环来遍历每一行和每一列，从第二行和第二列开始，因为第一行和第一列已经初始化了。
对于每个格子，我们判断它是否在第一行或第一列，如果是，那么它只能从左边或上面来，所以我们把左边或上面的值赋给它。如果不是，那么它可以从左边或上面来，所以我们把左边和上面的值相加赋给它。
最后，我们返回dp[m-1][n-1]，就是右下角的值，也就是从左上角到右下角的路径数。
具体实现
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n]; // 创建二维数组
dp[0][0] = 1; // 初始条件
for (int i = 0; i < m; i++) { // 遍历每一行
for (int j = 0; j < n; j++) { // 遍历每一列
if (i == 0 && j == 0) continue; // 跳过左上角
if (i == 0) { // 第一行，只能从左边来
dp[i][j] = dp[i][j-1];
} else if (j == 0) { // 第一列，只能从上面来
dp[i][j] = dp[i-1][j];
} else { // 其他情况，从左边或上面来
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1]; // 返回右下角的值
}
}
3. 总结