LeetCode 118. Pascal's Triangle [Easy] [C++] 解題筆記

 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

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

想法:

    這題就是要我們求帕斯卡三角形，基本上就是用 DP，當前 row 的 col i 會等於上一個 row 的 col i - 1 + col i

。

Complexity: O(1+2+...+numRows)

完整程式碼:

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