Pascal Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

Pascal’s triangle : To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1.

Given numRows = 5,

Return

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

思路:

一行一行生成。

Solution:

Time: O(n)
Space: O(n^2)

public class Solution {
    public ArrayList<ArrayList<Integer>> solve(int A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (A == 0) return result;
        ArrayList<Integer> first = new ArrayList<>();
        first.add(1);
        result.add(first);
        if (A == 1) return result;
        ArrayList<Integer> second = new ArrayList<>();
        second.add(1);
        second.add(1);
        result.add(second);
        if (A == 2) return result;
        for (int i = 3; i <= A; i ++) {
            ArrayList<Integer> curr = new ArrayList<>();
            for (int j = 0; j < i; j ++) {
                if (j == 0 || j == i - 1) {
                    curr.add(1);
                } else {
                    curr.add(result.get(i - 2).get(j - 1) + result.get(i - 2).get(j));
                }
            }
            result.add(curr);
        }
        return result;
    }
}