20201209
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
不同路径
例如,上图是一个 7 x 3 的网格。有多少可能的路径?
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
输入: m = 7, n = 3
输出: 28
提示:
抛砖引玉
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
const dp = Array(m).fill(Array(n).fill(1))
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
}
}
return dp[m - 1][n - 1]
}
观察上面的逻辑,dp[i][j]只与 dp[i][j-1] 、 dp[i-1][j],那么针对行(或者列)的累加到同一列(或者行)就能实现 dp 的降维
var uniquePaths = function(m, n) {
const dp = Array(n).fill(1)
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1]
}
}
return dp[n - 1]
}
从[0][0]到[m][n]过程中,需要移动 m+n−2 次,其中有 m−1 次向下移动,n−1 次向右移动
因此路径的总数,就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数,即组合数:
var uniquePaths = function(m, n) {
let _result = 1
for (let x = n, y = 1; y < m; ++x, ++y) {
_result = Math.floor((_result * x) / y)
}
return _result
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童