118.PascalsTriangle.md

tags: Array

#LeetCode 118 Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, Return

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

Diffculty Easy

Similar Problems [LeetCode 119] Pascal's Triangle II E

Analysis

先理解 Pascal Triangle 的特征：

• 第 k 层有 k 个元素
• 每层第一个以及最后一个元素值为 1
• 对于第 k（k > 2）层第 n（n > 1 && n < k）个元素 A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n]

Solutions

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        res.resize(numRows);
        for(int i = 0; i < numRows; i++) {
            res[i].resize(i + 1);           // 第 i 层有 i + 1 个元素
            res[i][0] = 1;
            res[i][res[i].size() - 1] = 1;
            for(int j = 1; j < res[i].size() - 1; ++j) {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};

Reference

http://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif?_=3887910