杨辉三角第 k 行如何用一维数组原地生成？（LeetCode 119）

简化版

杨辉三角第 k 行可以用一维数组从左到右初始化，再每轮从右往左更新：row[j] = row[j] + row[j-1]。必须从右往左，因为当前行的 row[j] 依赖上一行的 row[j] 和 row[j-1]，从左往右会覆盖还没用到的旧值。

详细版

List<Integer> getRow(int rowIndex) {
    List<Integer> row = new ArrayList<>();
    for (int i = 0; i <= rowIndex; i++) {
        row.add(1);
        for (int j = i - 1; j >= 1; j--) {
            row.set(j, row.get(j) + row.get(j - 1));
        }
    }
    return row;
}

例如第 4 行是 [1,4,6,4,1]。空间复杂度 O(k)，比构建整个三角形的 O(k^2) 更省。

完整版教学

一、杨辉三角的递推关系

杨辉三角每个非边界元素都等于上一行相邻两个元素之和：

第 0 行:       1
第 1 行:      1 1
第 2 行:     1 2 1
第 3 行:    1 3 3 1
第 4 行:   1 4 6 4 1

递推式是：

C(i,j) = C(i-1,j-1) + C(i-1,j)

二、为什么可以只用一维数组

要算当前行，只需要上一行，不需要更早的行。进一步看，当前行可以直接写回同一个数组。

目标元素	依赖旧值
`row[j]` 新值	旧 `row[j]`
`row[j-1]`	旧 `row[j-1]`

只要更新顺序不破坏旧值，就能原地完成。

关键点：一维 DP 能不能原地，核心看更新时是否会覆盖后续还要使用的旧状态。

三、为什么必须从右往左更新

假设上一行是：

[1, 3, 3, 1]

要更新成第 4 行。如果从左往右，row[1] 会先变成 4，后面算 row[2] 时就会错误使用新 row[1]。

从右往左：

row[3] = old row[3] + old row[2]
row[2] = old row[2] + old row[1]
row[1] = old row[1] + old row[0]

旧值都还在。

四、边界为什么都是 1

每一行的第一个和最后一个元素都是 1。代码里每进入新行先 row.add(1)，自然补上最右边界；最左边 row[0] 从始至终保持 1。

row.add(1);
for (int j = i - 1; j >= 1; j--) {
    row.set(j, row.get(j) + row.get(j - 1));
}

循环不更新 j=0，也不更新最后新加的 1。

五、组合数视角

第 k 行第 j 个数就是组合数 C(k,j)。也可以用公式迭代：

C(k,j) = C(k,j-1) * (k-j+1) / j

这种写法空间也低，但要注意整数溢出和除法顺序。DP 写法更直观。

六、复杂度分析

外层生成 k+1 行，内层总更新次数是：

1 + 2 + ... + k = O(k^2)

空间只存一行，O(k)。

七、常见误区与追问

误区：一维更新从左往右。 会覆盖上一行旧值，导致结果偏大。
误区：把 rowIndex 当成行数少算一行。 第 0 行是 [1]，所以要循环到 rowIndex。
误区：更新边界元素。 两侧边界恒为 1，不参与递推。
追问：为什么空间是 O(k)？ 只保留目标行长度的数组。
追问：能不能用组合数公式？ 可以，但要注意溢出和整除顺序。
追问：时间能否到 O(k)？ 公式法可以生成一行 O(k)，DP 一维法是 O(k^2)。

八、加强记忆

杨辉三角一维写法的核心是“右往左”。新行先补一个 1，再从 i-1 倒着加到 1。只要能解释从左往右会覆盖旧状态，这题就讲透了。

简化版

详细版