Leetcode Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

---

解题思路：

为了达到O(k)的空间复杂度要求，那么就要从右向左生成结果。相当于你提前把上一行的计算出来，当前行就可以用上一次计算出的结果计算了。

---

Java code:

public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        if(rowIndex < 0) {
            return result;
        }
        result.add(1);
        for(int i = 1; i <= rowIndex; i++) {
            for(int j = result.size()-2; j >= 0; j--) {  //from right to left
                result.set(j+1, result.get(j) + result.get(j+1));
            }
            result.add(1);
        }
        return result;
    }

---

Reference:

1. http://www.programcreek.com/2014/04/leetcode-pascals-triangle-ii-java/