不同路径
七崽爱吃小饼干2026/02/09阅读 0
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
codeType
输入：m = 3, n = 7
输出：28
示例 2：
codeType
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
codeType
输入：m = 7, n = 3
输出：28
示例 4：
codeType
输入：m = 3, n = 3
输出：6
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10
解法
ts
function uniquePaths(m: number, n: number): number {
// dp[i][j]表示到达i,j的路径数
// dp[i][j] = dp[i-1][j] + dp[i][j-1]
const dp = new Array(n).fill(0).map(() => new Array(m).fill(0))
for(let i = 0; i < n; i++){
for(let j = 0; j < m; j++){
if(i === 0 && j === 0){
dp[i][j] = 1
continue
}
dp[i][j] = (i === 0 ? 0 : dp[i - 1][j]) + (j === 0 ? 0 : dp[i][j - 1])
}
}
return dp[n - 1][m - 1]
};