62. Unique Paths

Leetcode link

题目简介

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

题目给我们一个 m 行 n 列的棋盘

要求我们计算出从左上角走到右下角总共有多少种可能的不重复路线

解题思路

假设 m=2, n=2 我们可以得到如下状态图

首先我们到达左上角的路径只有一条（因为是初始状态）

在左上角的时候我们可以选择向右走或者向下走，所以两个对应格子各自是 1

有趣的是右下角格子的路径数量，是等于它上面格子的路线数量 + 左边格子路线数量

所以我们可以得到一个状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

有了状态转移方程后，我们只需要从 dp[0][0]（也就是左上角）开始依次更新 dp 数组直到求出 dp[m-1][n-1] 的值即是答案

为了方便计算，我们可以声明一个 m+1 * n+1 的 dp 棋盘，并把第一行跟第一列设置为 0

以上，就是动态规划的思路

Javascript

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    const dp = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0))
    dp[1][1] = 1

    for (let row = 1; row <= m; row++) {
        for (let col = 1; col <= n; col++) {
            dp[row][col] += dp[row - 1][col] + dp[row][col - 1]
        }
    }

    return dp[m][n]
};