從左上角起始節(jié)點(diǎn)到末尾節(jié)點(diǎn)颜价，有多少種不同的可能。
動(dòng)態(tài)規(guī)劃方法
找出遞推關(guān)系 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- 時(shí)間復(fù)雜度O(mn)，空間復(fù)雜度O(mn)
- Runtime: 80 ms, faster than 71.70%
- Memory Usage: 37.9 MB, less than 99.36%
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
var dp = Array(m).fill().map(item => Array(n).fill(1))
for(var i = 1; i < m; i++){
for(var j = 1; j < n; j++){
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
}
}
return dp[m - 1][n - 1]
};
組合數(shù)學(xué)
從左上角到右下角的過(guò)程具则，需要移動(dòng) m + n - 2 次苛骨，m - 1 次向下移動(dòng)，n - 1次向右移動(dòng)顾稀，組合數(shù)為
組合公式
- 時(shí)間復(fù)雜度O(m)达罗，空間復(fù)雜度O(1)
- Runtime: 80 ms, faster than 71.70%
- Memory Usage: 38.3 MB, less than 90.33%
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
let res = 1
for(let x = n, y = 1; y < m; x++, y++) {
res = res * x / y
}
return res
};
