118. 杨辉三角

难度：🟢 Easy | 标签：动归 | 状态：⬜ LeetCode 链接

思路

row[i][j] = row[i-1][j-1] + row[i-1][j]，两端为 1。

代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        for (int i = 0; i < numRows; ++i) {
            res[i].assign(i + 1, 1);
            for (int j = 1; j < i; ++j) {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};

复杂度

• 时间 O(n²)，空间 O(n²)

易错 / 回顾

• 内层循环 j ∈ [1, i)，两端是 1
• 119 只要第 K 行：滚动数组从后往前更新