原题地址：不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明： m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
动态规划
用一个二维数组$dp$来存储每个格子到达右下角的路径数量。由于只能向右或向下走，所以我们从右下角开始，每个格子的路径数量都等于它右边一格的路径数量与下面一格的路径数量之和。
具体的实现代码如下：
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
const uniquePaths1 = function(m, n) {
// 二维数组，用来记录每个格子到达右下角的路径数量，初始为0
let dp = new Array(n);
for (let i = 0; i < n; i ++) {
dp[i] = new Array(m).fill(0);
}
// 右下角本身有一条路径到达它自己
dp[n-1][m-1] = 1;
for (let i = n - 1; i >= 0; i --) {
for (let j = m - 1; j >= 0; j --) {
// 下方还有格子就加上下面一格的路径数量
if (i < n - 1) {
dp[i][j] += dp[i + 1][j];
}
// 右边还有格子就加上右边一格的路径数量
if (j < m - 1) {
dp[i][j] += dp[i][j + 1];
}
}
}
// 返回左上角格子的路径数量
return dp[0][0];
};
测试：
let start = new Date();
const test = uniquePaths1;
console.log(test(3, 2)); // 3
console.log(test(7, 3)); // 28
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 每个格子都需要确定路径数量，时间复杂度为$O(MN)$
空间复杂度： 需要一个额外的$dp$数组，空间复杂度为$O(MN)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 17,2019