62. 不同路径

[Geekhyt]

原题链接

动态规划

定义状态

先明确题意，机器人只能选择向下或者向右走。

使用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)