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

1.数学方法直接根据排列组合求出公式

function uniquePaths( m ,  n ) {
    // write code here
    let A1,A2,A3;
    function jc(num){
        let res = 1;
        for(let i = 0; i < num; i ++){
            res *= i + 1;
        }
        return res;
    }
    A1 = jc(m - 1);
    A2 = jc(n - 1);
    A3 = jc(m + n - 2);
    let res = Math.round(A3 / (A1 * A2));
    return res;
}
module.exports = {
    uniquePaths : uniquePaths
};

2.dp动态规划

function uniquePaths( m ,  n ) {
    // write code here
    //初始化
    let dp = [];
    for(let i = 0; i < m; i ++){
        dp[i] = 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
};

对于二维数组初始化的部分有其他写法，运行时长自测大差不差。

let dp = Array(m).fill().map(item => Array(n).fill(1));

let dp = Array(m).fill().map(item => Array(n));
for(let i = 0; i < m; i ++){
  dp[i][0] = 1;
}
for(let i = 0; i < n; i ++){
  dp[0][i] = 1;
}