# 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]]

### 从左到右​

// Pascal's Triangle// 时间复杂度O(n^2)，空间复杂度O(n)public class Solution {    public List<List<Integer>> generate(int numRows) {        List<List<Integer>> result = new ArrayList<>();        if(numRows == 0) return result;        result.add(new ArrayList<>(Arrays.asList(1))); //first row        for(int i = 2; i <= numRows; ++i) {            Integer[] current = new Integer[i]; // 本行            Arrays.fill(current, 1);            List<Integer> prev = result.get(i - 2); // 上一行            for(int j = 1; j < i - 1; ++j) {                current[j] = prev.get(j-1) + prev.get(j); // 左上角和右上角之和            }            result.add(new ArrayList<>(Arrays.asList(current)));        }        return result;    }}

### 从右到左​

// Pascal's Triangle// 时间复杂度O(n^2)，空间复杂度O(n)public class Solution {    public List<List<Integer>> generate(int numRows) {        List<List<Integer>> result = new ArrayList<>();        List<Integer> array = new ArrayList<>();        for (int i = 1; i <= numRows; i++) {            for (int j = i - 2; j > 0; j--) {                array.set(j, array.get(j - 1) + array.get(j));            }            array.add(1);            result.add(new ArrayList<Integer>(array));        }        return result;    }}