杨辉三角 | 秋招知识库

把杨辉三角的每一排左对齐：

\begin{aligned} [1] \\ [1, 1] \\ [1, 2, 1] \\ [1, 3, 3, 1] \\ [1, 4, 6, 4, 1] \end{aligned}

设要计算的二维数组是 $c$ ，计算方法如下：

每一排的第一个数和最后一个数都是 $1$ ，即 $c [i] [0] = c [i] [i] = 1$ 。
其余数字，等于左上方的数，加上正上方的数，即 $c [i] [j] = c [i - 1] [j - 1] + c [i - 1] [j]$ 。例如 $4 = 1 + 3, 6 = 3 + 3$ 等。

Python 解法1C++ 解法1

python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        c = [[1] * (i + 1) for i in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, i):
                # 左上方的数 + 正上方的数
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
        return c

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> c(numRows);
        for (int i = 0; i < numRows; i++) {
            c[i].resize(i + 1, 1);
            for (int j = 1; j < i; j++) {
                // 左上方的数 + 正上方的数
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
        return c;
    }
};

复杂度分析

时间复杂度： $O ({numRows}^{2})$ 。
空间复杂度： $O (1)$ 。返回值不计入。

附：如何理解这个式子

递推式

c [i] [j] = c [i - 1] [j - 1] + c [i - 1] [j]

本质上是一个组合数恒等式，其中 $c [i] [j]$ 表示从 $i$ 个不同物品中选出 $j$ 个物品的方案数。

如何理解上式呢？考虑其中某个物品选或不选：

选：问题变成从剩下 $i - 1$ 个不同物品中选出 $j - 1$ 个物品的方案数，即 $c [i - 1] [j - 1]$ 。
不选：问题变成从剩下 $i - 1$ 个不同物品中选出 $j$ 个物品的方案数，即 $c [i - 1] [j]$ 。

二者相加（加法原理），得

c [i] [j] = c [i - 1] [j - 1] + c [i - 1] [j]

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

附：如何理解这个式子 ​

分类题单 ​

复杂度分析

附：如何理解这个式子

分类题单