0119. Pascal's Triangle II
==========================
题目信息
--------
:题号: 0119. 杨辉三角 II
:难度: Easy
:主题: 数组、动态规划、逆序更新、组合数
:原题: `LeetCode 0119 `_
:重点: 从保存全部历史行压缩为原地滚动数组,再利用目标行的组合数结构删除前面各行的构造
题目重述
--------
给定非负整数 ``rowIndex``,返回杨辉三角中零基编号为 ``rowIndex`` 的一整行。第 ``0`` 行是 ``[1]``;
第 ``rowIndex`` 行共有 ``rowIndex + 1`` 个元素,首尾为 ``1``,内部元素由上一行相邻两项之和得到。
约束为 ``0 <= rowIndex <= 33``。题目只要求目标行,不需要返回或保留之前各行。
自建示例
--------
* ``rowIndex = 6`` 时返回 ``[1,6,15,20,15,6,1]``;
* ``rowIndex = 2`` 时返回 ``[1,2,1]``;
* ``rowIndex = 1`` 时返回 ``[1,1]``;
* ``rowIndex = 0`` 时返回 ``[1]``,不需要执行任何转移。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
std::vector buildFullTriangle(int rowIndex) {
std::vector> triangle;
for (int row = 0; row <= rowIndex; ++row) {
std::vector current(row + 1, 1);
if (row > 0) {
for (int column = 1; column < row; ++column) {
current[column] = triangle.back()[column - 1] + triangle.back()[column];
}
}
triangle.push_back(std::move(current));
}
return triangle.back();
}
std::vector rollingRow(int rowIndex) {
std::vector row(rowIndex + 1);
row[0] = 1;
for (int currentRow = 1; currentRow <= rowIndex; ++currentRow) {
for (int column = currentRow; column >= 1; --column) {
row[column] += row[column - 1];
}
}
return row;
}
std::vector combinationRow(int rowIndex) {
std::vector row(rowIndex + 1);
long long value = 1;
for (int column = 0; column <= rowIndex; ++column) {
row[column] = static_cast(value);
if (column < rowIndex) {
value = value * (rowIndex - column) / (column + 1);
}
}
return row;
}
public:
std::vector getRow(int rowIndex) {
return combinationRow(rowIndex);
}
};
题解
----
完整三角形基线
~~~~~~~~~~~~~~
最直接的正确方案是从第 ``0`` 行开始,按“首尾为 ``1``、内部等于上一行相邻父项之和”依次构造到目标行。
``buildFullTriangle`` 保存每一行,最终返回最后一行。依赖顺序自上而下,所有父项在读取前都已正确计算。
但历史行只服务于下一行,完成目标后全部被丢弃。保存三角形需要 ``1 + 2 + ... + (rowIndex + 1)`` 个整数,
而返回值只有 ``rowIndex + 1`` 个。首先应删除的是不属于输出的历史行。
一维逆序滚动
~~~~~~~~~~~~
上一行与当前行的关系为:
.. code-block:: text
new[column] = old[column] + old[column - 1]
预先分配长度 ``rowIndex + 1`` 的数组,令 ``row[0] = 1``,其余位置为 ``0``。每轮只更新当前行会使用的
前缀,数组便可同时表示旧行和新行。
更新必须从右向左。计算 ``row[column]`` 时,右侧当前位置仍保存 ``old[column]``,左邻位置也还没有在本轮
修改,因而能读取 ``old[column - 1]``。若从左向右,左邻已经变成 ``new[column - 1]``,同一轮的新值会
被再次使用,递推关系被改变。
尾部的 ``1`` 也无需单独赋值:进入第 ``currentRow`` 轮前,``row[currentRow]`` 仍为 ``0``;本轮第一个
逆序更新把它加上上一行末尾的 ``1``,自然得到新行尾。
.. list-table::
:header-rows: 1
* - 完成行号
- 工作数组有效前缀
* - 0
- ``[1]``
* - 1
- ``[1,1]``
* - 2
- ``[1,2,1]``
* - 3
- ``[1,3,3,1]``
* - 4
- ``[1,4,6,4,1]``
``rollingRow`` 把空间从完整三角形的 ``O(rowIndex²)`` 压缩到返回数组本身,但仍要构造从第 ``0`` 行到目标
行的全部中间状态,总更新次数为 ``O(rowIndex²)``。
只构造目标行
~~~~~~~~~~~~
杨辉三角第 ``rowIndex`` 行第 ``column`` 项也是组合数 ``C(rowIndex, column)``。相邻项满足:
.. code-block:: text
C(rowIndex, 0) = 1
C(rowIndex, column + 1) =
C(rowIndex, column) * (rowIndex - column) / (column + 1)
因此已知当前 ``value`` 后,可以在常数时间得到下一列,不再构造任何前置行。组合数关系保证每步整除;代码
先乘后除,并用 ``long long`` 保存中间乘积,避免虽然最终元素适合 ``int``,乘法过程却超出 32 位。
对 ``rowIndex = 6``,状态依次为:
.. code-block:: text
1
1 * 6 / 1 = 6
6 * 5 / 2 = 15
15 * 4 / 3 = 20
20 * 3 / 4 = 15
15 * 2 / 5 = 6
6 * 1 / 6 = 1
这直接得到 ``[1,6,15,20,15,6,1]``。首尾和对称性都由同一递推自然产生,不需要特殊列分支。
主解与复杂度
~~~~~~~~~~~~
公开入口采用组合数递推,因为它把一维 DP 中仍然存在的全部前置行更新删除,时间从 ``O(rowIndex²)`` 降为
``O(rowIndex)``。代价是依赖组合数恒等式和较宽中间类型;若题目只提供局部父项关系,逆序滚动 DP 更通用。
完整三角形时间、空间均为 ``O(rowIndex²)``;滚动 DP 时间 ``O(rowIndex²)``、返回数组空间
``O(rowIndex)``;组合数主解时间 ``O(rowIndex)``,除返回数组外只用常数状态。返回数组本身需要
``O(rowIndex)`` 空间,无法再减少。