LeetCode 「中等」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
解答
动态规划
问题的本质
- 机器人从左上角到右下角的每一步，只能向右或向下移动，这意味着每个位置的路径数取决于其上方和左方的位置
- 动态规划可以很好地利用这种“状态转移”关系，通过计算每个位置的路径数，最终得到终点的路径数
关键思路
- 定义状态
- 设
dp[i][j]表示从起点(0, 0)到达位置(i, j)的不同路径数
- 状态转移方程
- 由于机器人只能从上方或者左方到达当前位置，因此：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
- 初始化
- 第一行和第一列的所有位置都只有一条路径可以到达（只能一直向右或一直向下），因此初始化为 1：
dp[0][j] = 1;
dp[i][0] = 1;
- 计算结果
- 遍历整个网格，根据状态转移方程计算每个位置的路径数，最终
dp[m - 1][n - 1]即为结果
Code
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// 创建一个 m x n 的二维数组 dp，初始化为 1
const dp = Array.from({ length: m }, () => Array(n).fill(1));
// 遍历网格，计算每个位置的路径数
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// 返回右下角的路径数
return dp[m - 1][n - 1];
};