62. 不同路径
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例：输入：m = 3, n = 7 输出：28；输入：m = 3, n = 2 输出：3；输入：m = 7, n = 3 输出：28；输入：m = 3, n = 3 输出：6
考点：概率论/动态规划
解答：
-
方法一：
时间复杂度：O(mn)，空间复杂度：O(mn) - 即为存储所有状态需要的空间
- 优化点
- 注意到 f(i,j)f(i, j)f(i,j) 仅与第 i 行和第 i−1行的状态有关，因此我们可以使用 滚动数组 代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))
- 优化点
var uniquePaths = function(m, n) {
// 建立一个 m * n 的表格
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
// 将表格中的两边设置为 1
for(let i = 0; i < m; i++) {
f[i][0] = 1;
}
for(let j = 0; j < n; j++) {
f[0][j] = 1;
}
// 累加每条路径的可能性
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
//
return f[m-1][n-1]
};
- 方法二：
我们需要移动 m+n-2 次，其中 m-1 向下移动，n-1向右移动 -> 路径的移动总数 = 从 m+n-2 次移动中选择 m-1 次向下移动的方案
时间复杂度：O(m)，空间复杂度：O(1)
- 优化点
- 由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))
var uniquePaths = function(m, n) {
let ans = 1;
for (let x = n, y = 1; y < m; ++x, ++y) {
ans = Math.floor(ans * x / y);
}
return ans;
};