Kth Row of Pascal's Triangle

Given an index k, return the kth row of the 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.

Input : k = 3

Return : [1,3,3,1]

思路:

一行一行算，重用上一行的结果。

Solution:

Time: O(n)
Space: O(k)

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