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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param m int整型
 * @param n int整型
 * @return int整型
 */
function uniquePaths(m, n) {
    // write code here
    // 动态规划，每一次到某一个点的路径数量，等于上面路径的数量加左边路径的数量
    // 即 dp[i][j] = dp[i-1][j] +dp[i][j-1]
    let dp = [new Array(n + 1).fill(0)];
    for (let i = 1; i < m + 1; i++) {
        dp.push([]);
        for (let j = 0; j < n + 1; j++) {
            if (j == 0) {
                dp[i].push(0);
                continue;
            }
            if (j == 1&&i==1) {
                dp[i].push(1);
                continue;
            }
            dp[i].push(dp[i - 1][j] + dp[i][j - 1]);
        }
    }
    console.log(dp);
    return dp[m][n];
}
module.exports = {
    uniquePaths: uniquePaths,
};