Given a non-negative integer numRows, generate the former numRows of the “Yang Hui triangle”.

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example 1:

Input:

numRows = 5

Output:

[[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]]

Example 2:

Input:

numRows = 1

Output:

[[1]]  

Tip:

  • 1 <= numRows <= 30

Code:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int i = 0; i < numRows; ++i) {
            ans[i].resize(i + 1);
            ans[i][0] = ans[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ans[i][j] = ans[i - 1][j] + ans[i - 1][j - 1]; }}returnans; }};Copy the code

Ideas:

Yang Hui triangle is a geometric arrangement of binomial coefficients in triangles. It is one of the outstanding research achievements of ancient Chinese mathematics. It graphically represents the binomial coefficient and intuitively reflects some algebraic properties of combination number. It is a combination of discrete number and form.

Yang Hui triangle has the following properties:

  1. The numbers in each row are symmetrical, starting at 1 and getting bigger and smaller and finally back to 1.

  2. The NTH line (numbered from 0) has n+1 terms, and the first n lines have n(n+1)2\frac{n(n+1)}{2}2n(n+1) numbers.

  3. The MTH number of row NTH (numbered from 0) can be expressed as a combination number C(n,m), denoted as Cnm\mathcal{C}_n^mCnm or (nm)\binom{n}{m}(mn), that is, the combination number of m elements from n distinct elements. We can express it by the formula: Cnm=n! m! X (n – m)! \mathcal{C}_n^m=\dfrac{n! }{m! \times (n-m)! }Cnm=m! X (n – m)! n!

  4. Each number is equal to the sum of the left and right digits in the previous row. That is, the iith number in the NNTH row is equal to the sum of the iith number and the iith number in the n-1n−1 row. This is also one of the nature of the combinatorial number, namely the Cni = Cn – 1 + Cn I – I – 1 1 \ mathcal {C} _n ^ I = \ mathcal {C} _ {n – 1} ^ I + \ mathcal {C} _ {n – 1} ^ {1} I – the Cni Cn – 1 = I + Cn I – 1-1.

  5. The coefficients in the (a+b)n(a+b)^n(a+b)n expansion (binomial expansion) correspond in turn to each term in the NTH row of Yang Hui’s triangle.

By property 4, we can compute the Yang Hui triangle line by line. Every time we evaluate row I, we can evaluate row I plus 1 in linear time complexity.

Complexity analysis:

  • Time complexity: O(numRows2)
  • Space complexity: O(1). The space footprint of the return value is not considered.