pascals-triangle

力扣

思路 💥

每一行的第一个元素和最后一个元素均为1，中间元素有：

假设上一行元素为 prev 数组， 本行为 next数组， 则有：

则，使用该递推公式即可。

Code 🐘

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        vector<int> prev = {1}, next;
        ans.push_back(prev);
        int i = 2;
        while(i <= numRows){
            // 重新初始化，扩充元素
            next.resize(i,1);
            for(int j = 1; j < i -1; j++){
                next[j] = prev[j-1] + prev[j];
            }
            prev = next;
            ans.push_back(next);
            i++;
        }

        return ans;
    }
};

复杂度分析 🥇

时间复杂度	空间复杂度
O(N^2)	O(N)