【LetMeFly】118. Yang hui triangle

Force button topic link ：https://leetcode.cn/problems/pascals-triangle/

Given a nonnegative integer  numRows, Generate 「 Yang hui triangle 」 Before  numRows  That's ok .

stay 「 Yang hui triangle 」 in , Each number is the sum of the numbers at the top left and right of it .

Example 1:

 Input : numRows = 5
 Output : [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example  2:

 Input : numRows = 1
 Output : [[1]]

Tips :

• 1 <= numRows <= 30

Method 1 ： Dynamic programming

We use it vector<vector<int>> ans To store Yang Hui triangle .

initialization The first line of Yang Hui triangle （ans.push_back({1})）

And then from $2$ OK, let's start （ Subscript $i$ from $1$ Start ）, Constantly generate each line .

The first i + 1 The generation method of rows is ：

First add the first element to this line $1$（ans.push_back({1})）

And then from the $2$ Elements start （ Subscript $j$ from $1$ Start ）, Until the previous element of the last element in this line , The first i + 1 OK, No j + 1 Elements are equal to the sum of the corresponding two elements in the previous line （ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]）

Last , Add another... To the end of this line $1$ that will do .

If you don't understand , You can refer to the chapter of Yang Hui triangle $3$ OK, No $2$ Elements $3$ To study ：

When calculated to the third $3$ OK, No $2$ Element time ,$i=2,j=1$. here $ans[i][j]=ans[i-1][j-1]+ans[i-1][j]=1+1=2$, Note No $3$ OK, No $2$ The value of each element is $2$.

• Time complexity $O(siz{e}^2)$
• Spatial complexity $O(1)$, The answer is not included in the algorithm space complexity

AC Code

C++

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

Running results ： It takes quite a little time

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125829159