0062. Unique Paths¶
题目信息¶
- 题号:
不同路径
- 难度:
Medium
- 主题:
动态规划、滚动数组、组合计数
- 原题:
- 重点:
从枚举移动序列,推导到复用位置状态,再利用固定步数直接组合计数
题目重述¶
机器人位于 m × n 网格的左上角 (0,0)。每一步只能向右或向下移动一格,求到达右下角
(m-1,n-1) 的不同路径数量。
两条路径只要移动序列不同,就视为不同路径。
约束为 1 <= m, n <= 100,并保证答案不超过 2 * 10^9。
自建示例¶
输入:m = 3, n = 4
输出:10
每条路径必须执行 2 次向下和 3 次向右,共 5 步。选择其中哪 2 个位置执行向下,共有
C(5,2) = 10 种路径。
输入:m = 1, n = 6
输出:1
只有一行时只能连续向右,路径唯一。
输入:m = 4, n = 5
输出:35
每条路径包含 3 次向下和 4 次向右,因此共有 C(7,3) = 35 种移动序列。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
int enumeratePaths(int row, int column, int rows, int columns) {
if (row == rows - 1 && column == columns - 1) return 1;
int paths = 0;
if (row + 1 < rows) {
paths += enumeratePaths(row + 1, column, rows, columns);
}
if (column + 1 < columns) {
paths += enumeratePaths(row, column + 1, rows, columns);
}
return paths;
}
int tableDp(int rows, int columns) {
std::vector<std::vector<int>> ways(
rows,
std::vector<int>(columns, 1)
);
for (int row = 1; row < rows; ++row) {
for (int column = 1; column < columns; ++column) {
ways[row][column] = ways[row - 1][column] +
ways[row][column - 1];
}
}
return ways[rows - 1][columns - 1];
}
int rollingDp(int rows, int columns) {
if (columns > rows) std::swap(rows, columns);
std::vector<int> ways(columns, 1);
for (int row = 1; row < rows; ++row) {
for (int column = 1; column < columns; ++column) {
ways[column] += ways[column - 1];
}
}
return ways[columns - 1];
}
int countByCombinations(int rows, int columns) {
const int totalSteps = rows + columns - 2;
const int chosenSteps = std::min(rows - 1, columns - 1);
long long combinations = 1;
for (int selected = 1; selected <= chosenSteps; ++selected) {
combinations = combinations *
(totalSteps - chosenSteps + selected) /
selected;
}
return static_cast<int>(combinations);
}
public:
int uniquePaths(int m, int n) {
return countByCombinations(m, n);
}
};
题解¶
枚举移动序列¶
从 (row,column) 出发时,递归尝试仍在网格内的向下和向右移动。到达右下角时返回 1,父状态把两个方向
返回的路径数相加。
enumeratePaths 直接描述了全部移动序列,但同一位置会被不同前缀反复到达。例如先右后下和先下后右都会
到达 (1,1),而从该位置到终点的剩余答案只由坐标决定,与此前路径无关。
递归状态因此应从“完整移动历史”压缩为“当前位置”。
位置路径数不变量¶
定义:
ways[row][column] = 从起点到达 (row,column) 的路径数量
内部位置的最后一步只有两种互斥来源:从上方下移,或从左侧右移。因此:
ways[row][column] = ways[row-1][column] + ways[row][column-1]
第一行只能连续向右,第一列只能连续向下,所以边界状态都为 1。1 × 1 网格中不移动也构成一条路径,
同样由这个初始化覆盖。
按从上到下、从左到右的顺序计算时,每个状态依赖的上方和左方都已经确定。处理完 (row,column) 后,
ways 中该位置保存的就是全部到达路径,不会遗漏或重复:每条路径按最后一步唯一归入两个来源之一。
对 3 × 4 网格,状态表为:
1 1 1 1
1 2 3 4
1 3 6 10
二维状态转移¶
tableDp 保存完整二维表。每个位置只计算一次,已经消除了递归树中对相同坐标的重复求解。
这个表仍保留了不再需要的旧行。计算当前行时,只会读取上一行同列和当前行左侧,更早的行不会再次参与 转移。
滚动数组压缩¶
一维数组 ways[column] 在一次更新前表示上一行同列的路径数,更新后表示当前行同列的路径数。
从左向右执行:
ways[column] += ways[column-1]
此时右操作数仍是上方状态,左侧元素已经更新为当前行左方状态,恰好对应二维转移。
扫描方向不能改为从右向左,否则 ways[column-1] 仍属于上一行。代码让较短维度作为数组长度,把辅助
空间压缩为 O(min(m,n))。
固定步数组合¶
从左上角到右下角,任意路径都必须恰好执行:
向下 m-1 次
向右 n-1 次
总步数 m+n-2
一条路径可以唯一表示为一串固定长度的动作。选择总步数中的 m-1 个位置放置向下动作,其余位置只能
放置向右动作;任意这样的选择也一定得到一条合法路径。因此路径与位置集合一一对应:
C(m+n-2, m-1) = C(m+n-2, n-1)
选择 min(m-1,n-1) 作为组合数的下标,可以减少循环次数。
逐步组合计算¶
令 total = m+n-2,choose = min(m-1,n-1)。代码依次计算:
C(total-choose+selected, selected)
第 selected 轮开始前保存上一项组合数。乘上新分子并除以 selected 后,结果正好是下一项组合数,
所以每轮除法都整除,不需要浮点数。
题目保证最终答案不超过 2 * 10^9。中间组合数单调增长且不超过最终答案,乘法使用 long long,能够
安全容纳本题范围内的中间结果。
方法关系¶
四种方法处理的是同一棵路径决策树:
递归枚举:逐条访问根到叶路径
二维 DP:合并到达同一坐标的重复子问题
滚动 DP:删除转移不再依赖的旧行
组合计数:利用所有路径的两类步数固定,直接计算叶子数量
主入口调用 countByCombinations,因为它不需要建立网格状态,并且直接表达路径与动作位置集合的一一对应。
边界处理¶
当 m = 1 或 n = 1 时,chosenSteps = 0,组合循环不执行并返回 1,表示只有一条直线路径。
当 m = n = 1 时,总步数为 0,同样返回 1。所有方法都把“不移动”视为从起点到终点的唯一合法路径。
复杂度分析¶
朴素递归的搜索树为指数规模,递归深度为 O(m+n)。
二维动态规划时间和空间均为 O(mn)。滚动数组时间为 O(mn),额外空间为
O(min(m,n))。
组合方法循环 min(m-1,n-1) 次,时间为 O(min(m,n)),额外空间为 O(1)。