题解 | #不同路径的数目(一)#

动态规划思路

题目所求的是左上角到右下角的所有路径数量，那么中间状态为左上角到地图中任意方格的所有路径数量，由于机器人只能往下或者往右移动，因此任意方格的路径数量只跟上一方格和左一方格的路径数量有关，按照这两个方格状态转移到最终方格的路径数量即可。

最小子问题

当地图大小为1xn或者mx1时，所有方格的路径数量只有1，因此二维dp表的初始状态为当i=0或j=0时为1。

状态转移方程

由于由于机器人只能往下或者往右移动，因此任意方格的路径数量只跟上一方格和左一方格的路径数量有关，因此dp[i][j] = dp[i-1][j] + dp[i]][j-1]

/**
 *
 * @param m int整型
 * @param n int整型
 * @return int整型
 */
function uniquePaths( m ,  n ) {
    // write code here
    const dp = Array.from(new Array(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];
}
module.exports = {
    uniquePaths: uniquePaths,
};