littlearAppearance
题目描述
62.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
| 🤖️（start） | ||||||
|---|---|---|---|---|---|---|
| ✨（Finish） |
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
提示
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
思路
动态规划：
| dp[0][0] | ||||||
|---|---|---|---|---|---|---|
| dp[i-1][j] | ||||||
| dp[i][j-1] | dp[i][j] |
- 确定
dp[i][j]为从[0, 0]到[i, j]有dp[i][j]条不同的路径 - 因为机器人只能
向右或向下走，所以能到达dp[i][j]的只有dp[i-1][j]和dp[i][j-1]两条路径， 推出状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1] - 初始化
dp，因为第一行和第一列只有一种方式能到达，所以可以将第一行和第一列初始化为1
| dp[0][0] | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 1 | dp[i-1][j] | |||||
| 1 | dp[i][j-1] | dp[i][j] |
- 依次遍历行、列求出数据最后返回
dp[i][j]即可
| dp[0][0] | 1⬇️ | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 1➡️ | 2 | 3 | 4 | 5 | 6 | dp[i-1][j] = 7 |
| 1 | 3 | 6 | 10 | 15 | dp[i][j-1] = 21 | dp[i][j] = 28 |
题解
二维数组
javascript
const uniquePaths = function(m, n){
// 构建m行n列的二维数组
let dp = Array(m).fill(0).map(item=>Array(n).fill(0))
// 初始化第一列
for(let i =0; i<m; i++){
dp[i][0] = 1
}
// 初始化第一行
for(let j =0; j<n; j++){
dp[0][j] = 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]
}
优化
| 1 | 1⬇️ | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 1➡️ | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 3 | 6(上一行当前位置=3，当前位置前一列的值为3) | 10 | 15 | 21 | 28 |
通过上面的解法可以发现，当前位置的值其实等于上一行当前位置的值+当前位置前一列的值；
转换成一维数组就成为
第一次 `[1, 1 , 1 , 1 , 1 , 1 , 1 ]`
第二次 `[1, 2(1+1), 3(1+2), 4 , 5 , 6 , 7 ]`
第三次 `[1, 3(2+1), 6(3+3), 10(4+6), 15(5+10), 21(6+15), 28(7+21)]`
javascript
const uniquePaths = function(m, n){
//初始化长度为n的一维数组
let dp = Array(n).fill(1)
for(let i=1;i<m;i++){
for(let j=1;j<n;j++){
//当前位置=上一次的当前位置+当前位置前一列位置
dp[j] += dp[j-1]
}
}
return dp[n-1]
}