动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i][j] 的含义为 达到网格 i、j 处共有 dp[i][j] 条不同的路径；
确定递推公式：根据图解可知
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；
如何初始化 dp 数组：第一列、第一行初始化为 1；
确定遍历顺序：根据递推公式得知，需要从前向后遍历；
举例推导 dp 数组：
复杂度
-
时间复杂度：
O(M * N)； -
空间复杂度：
O(M * N)；
代码实现：
var uniquePaths = function (m, n) {
// 1. m*n 的矩阵
const dp = new Array(m).fill('').map(i => new Array(n).fill(''));
// 2. 初始化 dp 数组，第一行、第一列都赋值为 1
for (let i = 0; i < n; i++) dp[0][i] = 1;
for (let i = 0; i < m; i++) dp[i][0] = 1;
// 3. 根据递推公式，更新矩阵 dp[i][j] 的值
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];
};
动态规划（状态压缩）
解题思路
由于 dp[i][j] 仅与第 i 行和第 i − 1 行的状态有关，因此可以使用滚动数组代替代码中的二维数组，则递推公式改成
dp[j] = dp[j] + dp[j - 1]；i、j 要从 1 开始遍历，具体的递推过程如下：
复杂度
-
时间复杂度：
O(M * N)； -
空间复杂度：
O(N)；
代码实现
var uniquePaths = function (m, n) {
// 1. 定义一个 一维滚动数组
const dp = new Array(n).fill(1);
// 2. 根据递推公式，更新矩阵 dp[i][j] 的值
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 746. 使用最小花费爬楼梯
上一篇
评论
