LC118　杨辉三角¶

简单通过率 77.9%python3核心代码模式动态规划样例通过牛客 AC数组动态规划

牛客原题　源码

讲解章节：DP 入门

一句话

每行两端固定为 1，中间每格等于上一行的左上加右上，逐行推出去。

解题思路¶

这题考什么¶

递推关系题面已经写好了：每个数是它左上方与右上方之和。把它当成动态规划来读，状态就是格子本身。

状态定义：f[i][j] 表示第 i 行第 j 个数（两个下标都从 0 起）。转移方程：

f[i][j] = f[i-1][j-1] + f[i-1][j]        0 < j < i
f[i][0] = f[i][i] = 1                    每行两端

两端为什么是 1，而不是套用同一条转移式：第 j = 0 格没有左上方（f[i-1][-1] 不存在），第 j = i 格没有右上方（上一行长度只有 i，没有第 i 项）。缺一侧时只能继承单侧，而单侧继承下来的恰好一路都是 1。从组合意义上说，f[i][j] 就是组合数 C(i, j)，两端的 C(i, 0) 与 C(i, i) 都是 1。

这题的输出要求整张三角，所以不能像别的 DP 那样滚动压维—— 每一行都是答案的一部分，必须原样留下。计算时只需要上一行，但存储上必须把全部行都保留。

数据规模与复杂度¶

1 <= numRows <= 30。格子总数是 1 + 2 + ... + numRows = numRows * (numRows + 1) / 2， numRows = 30 时是 465 格，每格一次加法，规模上毫无压力。空间同为 O(numRows 的平方)，因为答案本身就有这么多个数。

第 30 行最大的数是 C(29, 14) = 77558760，不到 1e8，任何语言的 32 位整数都装得下，Python 更不必担心。

坑在哪¶

判题按严格比对，顺序就是答案。返回的是嵌套列表，但外层的行序（第 0 行在前）与内层的列序都由题目定死，不能因为「是列表的列表」就以为顺序无所谓。
两端的 1 不能进循环体去算。若把 j 的范围写成 0 到 i， j = 0 时会取到 prev[-1]——Python 的负下标是合法的，它会静默取到上一行的最后一个元素，不报错却算出完全错误的数，这是最难查的一类问题。
中间需要相加的位置只有 j = 1 到 i-1 共 i-1 个。i = 0 与 i = 1 这两行根本没有中间位置，整行都是 1，所以推导只在 i >= 2 时才有事可做。
cur = [1] * (i + 1) 先把整行填满 1，两端因此天然成型，不必再单独赋值。写成 [0] * (i + 1) 就必须记得手动把首尾改回 1，漏一处整个三角就废了。
每行长度是 i + 1 不是 i。第 0 行有 1 个数，下标偏移错一格会让所有行短一位，最后一行还会因为 prev 长度不够而下标越界。

样例复核¶

numRows = 5。

i = 0: [1]
i = 1: [1, 1]                     无中间位置
i = 2: [1, _, 1] -> cur[1] = 1 + 1 = 2      -> [1, 2, 1]
i = 3: cur[1] = 1 + 2 = 3, cur[2] = 2 + 1 = 3  -> [1, 3, 3, 1]
i = 4: cur[1] = 1+3 = 4, cur[2] = 3+3 = 6, cur[3] = 3+1 = 4  -> [1, 4, 6, 4, 1]

与期望输出 [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 完全一致。

参考实现¶

solutions/leetcode/LC118/sol.py
from typing import List, Optional


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 整张三角都是答案，所以不能滚动压维，每一行都要原样留下
        rows = []
        for i in range(numRows):
            # 第 i 行有 i + 1 个数。先整行填 1，两端就此定型：
            # 首格没有左上、末格没有右上，只能继承单侧，而单侧继承下来正是 1
            cur = [1] * (i + 1)
            # 第 0、1 行整行都是两端，没有中间位置可推，i >= 2 才进这一段
            if i >= 2:
                prev = rows[-1]                     # 上一行，长度 i，下标 0..i-1
                # 只推中间的 i-1 格；把范围放宽到 j = 0 会取到 prev[-1]，
                # Python 的负下标不报错却会静默取到上一行末尾，算出错值
                for j in range(1, i):
                    cur[j] = prev[j - 1] + prev[j]  # 左上 + 右上
            rows.append(cur)
        return rows

LC118 杨辉三角¶