[62] 不同路径

回溯

details

var uniquePaths = function (m, n) {
    let ans = 0;
    backtrack(0, 0);
    return ans;
    function backtrack(x, y) {
        if (x === m - 1 && y === n - 1) {
            ans++;
            return;
        }
        //
        if (x >= m || y >= n) {
            return;
        }
        backtrack(x + 1, y);
        backtrack(x, y + 1);
    }
};

记忆优化

var uniquePaths = function (m, n) {
    let map = new Map();
    return backtrack(0, 0);
    function backtrack(x, y) {
        if (x === m - 1 && y === n - 1) {
            return 1;
        }
        //
        if (x >= m || y >= n) {
            return 0;
        }
        const key = `${x}-${y}`;
        if (map.has(key)) return map.get(key);
        map.set(key, backtrack(x + 1, y) + backtrack(x, y + 1));
        return map.get(key);
    }
};

动态规划

details

var uniquePaths = function (m, n) {
    // 创建一个 m x n 的二维数组，初始化所有值为 1
    const dp = Array.from({ length: m }, () => Array(n).fill(1));

    // 遍历从 (1, 1) 到 (m-1, n-1) 的每个格子
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            // 更新 dp[i][j] 的值
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    // 返回右下角格子的路径数
    return dp[m - 1][n - 1];
};