本文的标题主要表示为「XX0000（甲乙丙丁）」的形式。其中前两个字母是题源平台的代码（如LC为LeetCode，CF为CodeForces，AC为AtCoder等），后方为题目编号和题目名称。

LC0801（杨辉三角）

完整的题干见此。本文的题解完成于8月1日，最早登于LeetCode国际服原题下。

  • 由于题目中numRows的范围不大，所以可以采取直接列举所有可能结果的方式。
  • 上述方法显然对numRows更大的情况不适用，因此寻找更一般的解法。
    • 首先注意到第二至五行的元素分别是(11),(121),(1331)\begin{pmatrix}1\\1\end{pmatrix},\begin{pmatrix}1\\2\\1\end{pmatrix}, \begin{pmatrix}1\\3\\3\\1\end{pmatrix}和(14641)\begin{pmatrix}1\\4\\6\\4\\1\end{pmatrix}，恰好分别是多项式a+b,(a+b)2,(a+b)3a+b, (a+b)^2, (a+b)^3和(a+b)4(a+b)^4展开后的各项系数；因此，初步猜测第ii行的元素应该均为(a+b)i(a+b)^i的展开式的系数。
    • 根据先前的数学知识知道(a+b)n=∑i=0nCnian−ibi,(a+b)^n=\sum_{i=0}^{n}\text{C}_n^ia^{n-i}b^i,因此杨辉三角中第nn行的第mm个元素AnmA_{nm}必然有Anm=CnmA_{nm}=\text{C}_n^m。
    • 我们知道组合数Cnm=n!m!(n−m)!,\text{C}_n^m=\frac{n!}{m!(n-m)!},因此Cnm=n!(m−1)!(n−m+1)!⋅(n−m+1)m=n−m+1mCnm−1\text{C}_n^m=\frac{\frac{n!}{(m-1)!(n-m+1)!}\cdot(n-m+1)}{m}=\frac{n-m+1}{m}\text{C}_n^{m-1}。据此，只要在一行中不断添加前一项的n−m+1m\frac{n-m+1}{m}倍对应值作为新的元素，就可以得到一整行的所有元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    std::vector<std::vector<int>> generate(int numRows) {
        std::vector<std::vector<int>> result;
        for (int i = 0; i < numRows; i++) {
            std::vector<int> row;
            row.push_back(1);
            for (int j = 1; j <= i; j++) {
                row.push_back(row.back() * (i + 1 - j) / j);
            }
            result.push_back(row);
        }
        return result;
    }
};

遭遇

先求组合数再加入数组导致时间超限

本题在最初写解时尝试使用递归函数先求出组合数Cnm\text{C}_n^m后直接添加进数组，但会因超出时间限制而错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long combination(int n, int m) {
        if(m==0 || m==n) return 1;
        return combination(n-1,m)+combination(n-1,m-1);
    }
    vector<vector<int>> generate(int numRows) {
        std::vector<std::vector<int>> result;
        for (int i = 0; i < numRows; i++) {
            std::vector<int> row;
            for (int j = 0; j <= i; j++) {
                row.push_back(combination(i, j));
            }
            result.push_back(row);
        }
        return result;
    }
};

出现时间超限的原因在于，每当向数组添加一次元素时就要进行一次时间复杂度为O(2n)O(2^n)的递归。这将使得整个程序的时间复杂度达到O(n2n)O(n2^n)，其中nn即numRows。