【数据结构入门_数组】 Leetcode 118. 杨辉三角

原题连接：Leetcode 118. Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

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

Example 2:

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

Constraints:

• 1 <= numRows <= 30

---

方法一：DP？

思路：

杨辉三角每一层，首先它的开头和结尾都是1
然后其中的元素由上一层的两个元素相加得到

c++代码：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);

        for(int i = 0; i < numRows; i++ ){
            // 第i层长度为i, 且第一个和最后一个元素都是1
            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-1] + ans[i-1][j];
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：

• 时间复杂度：O(numRows² )，计算次数为1+2+……+numRows
• 空间复杂度：O(1)， 返回值不计入辅助空间