不同路径

网格 DP 入门题：从上和左转移，求到右下角的路径数。

#resource / algorithm #type / snippet #status / growing #source / leetcode #algo / dp

[!info] related notes 动态规划网格 DP 与双序列 DP

不同路径

题目链接：https://leetcode.cn/problems/unique-paths/

状态

dp[i][j] 表示从左上角走到 (i, j) 的路径数。

转移

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

边界

第一行和第一列都只有 1 条路径。

样例

m = 3, n = 7

答案是 28。

JavaScript

var uniquePaths = function(m, n) {
    const dp = Array.from({ length: m }, () => new 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];
};