Unique Paths
一个机器人从一个有 m 行、n 列的网格左上角单元格出发，必须到达右下角单元格。每次移动，它可以向右或向下移动一个单元格。返回它可以走的不同路径数量。
函数
- minteger
- 网格中的行数
- ninteger
- 网格中的列数
- 返回值integer
- 从左上角单元格到右下角单元格的不同路径数量
约束条件
1 ≤ m, n ≤ 100- 答案最大为
2 × 109，因此可以用有符号 32 位整数表示。
示例
- 输入
- m = 3n = 4
- 输出
- 10
- 解释
- 每条路径都会向下移动 2 步，向右移动 3 步，总共移动 5 步。路径由 5 步中向下移动的 2 步决定，一共有 10 种选法。
- 输入
- m = 1n = 6
- 输出
- 1
- 解释
- 只有一行时，机器人只能向右移动 5 次，因此恰好只有一条路径。
- 输入
- m = 4n = 5
- 输出
- 35
- 解释
- 每条路径都有 3 步向下和 4 步向右。从 7 步中选出 3 步向下，共有 7 × 6 × 5 / 6 = 35 条路径。
进阶
对于 100 × 100 的网格，答案有 59 位数字。使用这个公式时，你要怎样返回它对 10^9+7 取模的结果？当除以 i 不再有效时，该怎么办？
提示
逐个打开提示，每个都会多透露一点。
机器人踏入某个格子之前，可能在哪里？
进入某个单元格的路径数，等于进入其上方单元格的路径数加上进入其左侧单元格的路径数。最上面一行和最左侧一列的每个单元格都恰好有一条路径。
按行从左到右填入计数，并保持数字排成一行。或者直接统计移动顺序：路径就是从
m+n-2步中选择m-1步向下走。
题解
逐条列出路径行不通：一个 17 × 17 的网格有 601,080,390 条路径。不如直接计数。到达某个单元格的路径数，等于到达它上方单元格的路径数加上到达它左侧单元格的路径数，这样只需遍历一遍就能填满表格。而一条路径不过是向下和向右移动的顺序，因此可以得到一个封闭公式。
用递归计算路径总数
结果正确，但无法在最大的测试中运行完毕
思路
机器人的最后一步要么是从上方的格子向下走，要么是从左侧的格子向右走。因此，uniquePaths(m, n) = uniquePaths(m-1, n) + uniquePaths(m, n-1)，而只有一行或一列的网格恰好有 1 条路径。每条路径的最后一步恰好是这两种走法之一，因此每条路径只会被计数一次。
每条路径最终都会到达一个返回 1 的基本情况，因此调用次数至少等于答案：一个 17 × 17 的网格需要超过 6 亿次调用。相同的小网格会被一遍又一遍地重复计算。
算法
- 如果
m或n是 1，就返回 1：唯一的路径是一条直线。 - 否则，统计最后一步向下的路径数量：
uniquePaths(m-1, n)。 - 统计最后一步向右的路径数量：
uniquePaths(m, n-1)。 - 返回它们的和。
def uniquePaths(m, n):
# One row or one column: the only path is a straight line
if m == 1 or n == 1:
return 1
# The last move came down from the row above or right from the column before
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)一次填充网格的一行
思路
递归会反复询问相同的 m × n 个单元格。按输入已就绪的顺序计算每个单元格一次。
状态：paths[r][c] 表示从左上角单元格到第 r 行、第 c 列单元格的路径数。递推关系：paths[r][c] = paths[r-1][c] + paths[r][c-1]，即从上方到达的路径数加上从左侧到达的路径数。基本情况：顶行和最左列的每个单元格都有 1 条路径。计算顺序：逐行计算，从左到右。对于 m = 3、n = 4，各行分别是 1 1 1 1、1 2 3 4、1 3 6 10，答案是 10。
填充过程只读取上一行，因此只需保留一行。在更新 row[c] 之前，它仍保存上方的路径数，而 row[c-1] 已经保存左侧的新路径数，因此 row[c] += row[c-1] 就是完整的递推关系，所需内存为 O(n)。
算法
- 创建一个包含
n个元素且元素全为 1 的row，作为顶行。 - 重复
m-1次，每次处理顶行下面的一行。 - 在每一行中，让
c从 1 递增到n-1，将row[c-1]加到row[c]上。row[0]保持为 1，也就是左列。 - 返回
row[n-1]。
def uniquePaths(m, n):
# row[c] counts the paths into column c of the current row.
# The top row is all 1s: the only way along it is straight right.
row = [1] * n
for _ in range(m - 1):
for c in range(1, n):
# Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
row[c] += row[c - 1]
return row[n - 1]用二项式系数统计移动次数
思路
每条路径都会向下移动 m-1 次，向右移动 n-1 次，总共移动 m+n-2 次，顺序可以任意排列。每种排列都是一条有效路径：向下移动次数不会超过 m-1 次，向右移动次数也不会超过 n-1 次，因此不会走出网格。所以，一条路径就是从所有移动中选出 m-1 次向下移动，答案是 C(m+n-2, m-1)。
不使用阶乘来计算组合数。令 N = m+n-2，k = min(m, n)-1，依次乘以 N-k+i，再除以 i，其中 i 从 1 到 k。第 i 步之后，结果为 C(N-k+i, i)，这是一个整数，因此每次除法都能整除。以 m = 3、n = 4 为例：1 × 4 / 1 = 4，然后 4 × 5 / 2 = 10。选择较短的一边，循环最多只需执行 99 步。
算法
- 设
N = m+n-2为移动次数，设k = min(m, n)-1。 - 将 64 位计数值设为 1。
- 对于从 1 到
k的i，将计数值乘以N-k+i，然后除以i。 - 返回计数值。
def uniquePaths(m, n):
# A path is m+n-2 moves; count the ways to choose which of them go down.
# Choose along the shorter side so the loop stays short.
moves = m + n - 2
k = min(m, n) - 1
count = 1
for i in range(1, k + 1):
# count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
count = count * (moves - k + i) // i
return count
易错点和边界情况
- 计算
(m+n-2)!，再除以另外两个阶乘。21! 已经超出 64 位范围，在 100 × 7 的网格中，m+n-2会达到 105。 - 像
count / i * (N-k+i)这样先除再乘。count不一定是i的倍数，因此除法会截断结果。 - 用 32 位整数保存累积乘积。在最后一次除法之前，它是答案的
k倍：对于 17 × 17 的网格，16 × 601,080,390，约为 9.6 × 10^9。 - 把顶行或左列的初始值设为 0，而不是 1。这样每个格子都会变成 0，但只有一行或一列的网格恰好有 1 条路径。
常见问题3
不同路径的时间复杂度是多少？
动态规划表需要 O(m × n) 时间；如果只保留一行，则需要 O(n) 空间。二项式公式需要 O(min(m, n)) 时间和 O(1) 空间。普通递归的调用次数至少与路径数一样多，而路径数相对于 m + n 呈指数增长。
有些单元格被阻挡时，如何求解 Unique Paths？
使用同一个表格，并将被阻挡单元格的计数设为 0，这样就不会有路径经过它。顶行和最左列不再全是 1：顶行中被阻挡单元格之后的每个单元格都没有路径。这个公式不再适用，因为它假设所有移动顺序都允许。
为什么“不同路径”表格与帕斯卡三角形相符？
每个单元格的值等于它上方单元格和左侧单元格的值之和，这就是沿对角线读取帕斯卡三角形的构造规则。第 r 行、第 c 列的单元格存储 C(r+c, r)，因此右下角的单元格存储 C(m+n-2, m-1)，也就是二项式公式。
def uniquePaths(m, n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
m = 3 n = 4
预期输出
10