0118. Pascal's Triangle ======================= 题目信息 -------- :题号: 0118. 杨辉三角 :难度: Easy :主题: 数组、递归定义、动态规划、二维结果构造 :原题: `LeetCode 0118 `_ :重点: 从逐项递归展开父节点,识别重叠子问题,再利用已经返回的上一行直接构造当前行 题目重述 -------- 给定正整数 ``numRows``,返回杨辉三角最上方的 ``numRows`` 行。使用零基行号时,第 ``row`` 行有 ``row + 1`` 个整数;首尾均为 ``1``,其余位置等于上一行中左上方与右上方两个相邻元素之和。 第一行是 ``[1]``,约束为 ``1 <= numRows <= 30``。返回结果必须包含每一行的独立数组。 自建示例 -------- * ``numRows = 6`` 时返回 ``[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]``; * ``numRows = 2`` 时返回 ``[[1],[1,1]]``,两行都没有需要父项相加的内部位置; * ``numRows = 1`` 时只返回 ``[[1]]``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: int recursiveValue(int row, int column) { if (column == 0 || column == row) { return 1; } return recursiveValue(row - 1, column - 1) + recursiveValue(row - 1, column); } std::vector> buildByRecursiveValues(int numRows) { std::vector> triangle; for (int row = 0; row < numRows; ++row) { std::vector current; current.reserve(row + 1); for (int column = 0; column <= row; ++column) { current.push_back(recursiveValue(row, column)); } triangle.push_back(std::move(current)); } return triangle; } std::vector> buildFromPreviousRow(int numRows) { std::vector> triangle; triangle.reserve(numRows); for (int row = 0; row < numRows; ++row) { std::vector current(row + 1, 1); if (row > 0) { const std::vector& previous = triangle.back(); for (int column = 1; column < row; ++column) { current[column] = previous[column - 1] + previous[column]; } } triangle.push_back(std::move(current)); } return triangle; } public: std::vector> generate(int numRows) { return buildFromPreviousRow(numRows); } }; 题解 ---- 逐项递归定义 ~~~~~~~~~~~~ 题目已经给出每个位置的直接定义。用 ``value(row, column)`` 表示零基坐标上的值: .. code-block:: text value(row, 0) = 1 value(row, row) = 1 value(row, column) = value(row - 1, column - 1) + value(row - 1, column) ``recursiveValue`` 原样执行这个定义,``buildByRecursiveValues`` 再对结果中的每个坐标调用它。递归最终都 到达两侧边界 ``1``,所以每个位置能够得到正确值,逐项填满后自然形成要求的全部行。 重复父项 ~~~~~~~~ 直接递归的问题是同一父项会被许多后代重复求解。计算中心位置时,左右递归树会再次展开共同祖先;输出第 ``row`` 行的多个位置时,又会各自从头展开前面各行。我们明明必须返回所有早期行,却没有复用已经算好的值。 记忆化能缓存 ``(row, column)``,但缓存表本身就是题目要求的三角形。与其从底部坐标向上递归查询,不如按 依赖方向从上到下构造,让上一行直接成为当前行的状态来源。 按行动态规划 ~~~~~~~~~~~~ ``buildFromPreviousRow`` 为第 ``row`` 行创建长度 ``row + 1`` 的独立向量,并先把全部位置初始化为 ``1``。 这样行首、行尾以及长度为 ``1``、``2`` 的小行都无需额外分支;只遍历 ``1 <= column < row`` 的内部位置, 从上一行读取两个父项。 当前行只能在上一行完成后构造。``previous`` 是 ``triangle.back()`` 的只读引用,而 ``current`` 是新分配的 行;计算期间不会覆盖父项,完成后再整体移动到结果。每行存储互不共享,后续构造不会修改历史行。 状态走读 ~~~~~~~~ .. list-table:: :header-rows: 1 * - ``row`` - 上一行 - 初始当前行 - 内部更新 - 完成行 * - 0 - 无 - ``[1]`` - 无 - ``[1]`` * - 1 - ``[1]`` - ``[1,1]`` - 无 - ``[1,1]`` * - 2 - ``[1,1]`` - ``[1,1,1]`` - ``1 + 1`` - ``[1,2,1]`` * - 3 - ``[1,2,1]`` - ``[1,1,1,1]`` - ``1 + 2``、``2 + 1`` - ``[1,3,3,1]`` * - 5 - ``[1,4,6,4,1]`` - 六个 1 - ``1+4``、``4+6``、``6+4``、``4+1`` - ``[1,5,10,10,5,1]`` 每个内部值只做一次加法。组合数公式也能独立计算一行,但需要乘除顺序和更宽中间类型;父项求和直接复用 题目给出的局部关系,更适合作为主解。 复杂度分析 ~~~~~~~~~~ 返回结果包含 ``1 + 2 + ... + numRows = Θ(numRows²)`` 个整数,任何方案至少要写入这些值。主解对每个位置 初始化或计算一次,时间 ``Θ(numRows²)``,返回空间也为 ``Θ(numRows²)``。当前行最长为 ``O(numRows)``, 完成后移动进结果,不产生另一份行副本。