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