不同路径
Unique Paths
本机进度仅保存在当前浏览器
题目描述
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 Start），机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角（标记为 Finish），问总共有多少条不同的路径。
示例：m = 3，n = 7，输出 28。
解题思路
- 状态 dp[i][j]：到达格 (i, j) 的路径数，只能从上方或左方转移，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
- 首行首列路径恒为 1；用一维滚动数组滚动更新即可，空间 O(n)。
- 组合数学视角：路径由 m-1 次下移与 n-1 次右移组成，答案为 C(m+n-2, m-1)，可直接计算。
参考实现
查看参考实现Python · 建议先自行作答
def uniquePaths(m, n):
# 一维滚动：dp[j] 为当前行到达第 j 列的路径数
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]