Repository navigation
62. 不同路径 #52
Description
动态规划
定义状态
先明确题意，机器人只能选择向下或者向右走。
使用dp[i][j]来表示终点坐标(i, j)。
- 向下走:
dp[i-1][j] - 向右走:
dp[i][j-1]
状态转移方程
dp[i][j] = dp[i-1][j] + dp[i][j-1]
处理边界
- i 和 j 分别等于 0 时，不满足要求需要被忽略。
- 初始条件 (0, 0) = 1，也就是终点与出发点重合。
const uniquePaths = (m, n) => {
const dp = Array.from(Array(n), () => Array(m).fill(1))
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
}
}
return dp[n - 1][m - 1]
}- 时间复杂度: O(m * n)
- 空间复杂度: O(m * n)
降维
每次只需要从上边和左边的位置转移过来，所以我们可以用一个一维数组来优化空间，滚动更新每行的路径数量。
- dp[j]: 第 x 行第j列的路径数量
状态转移方程
dp[j] = dp[j] + dp[j - 1]
第 i 行第 j 列位置的路径数量 = 第 i 行第 j - 1 列位置的路径数量 + 第 i - 1 行第 j 列位置的路径数量
const uniquePaths = function(m, n) {
const dp = new Array(n).fill(1)
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] = dp[j - 1] + dp[j]
}
}
return dp[n - 1]
}- 时间复杂度：O(m * n)
- 空间复杂度: O(n)
Activity