[leetcode]Pascal#39;s Triangle II

問題敘述性說明：

Given an index k, return the k^th 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?

思路：

the mth element of the nth row of the Pascal's triangle is C(n, m) = n!/(m! * (n-m)!)

C(n, m-1) = n!/((m-1)! * (n-m+1)!)

so C(n, m) = C(n, m-1) * (n-m+1) / m

In additional, C(n, m) == C(n, n-m)

代碼：

public List<Integer> getRow(int rowIndex) {if(rowIndex < 0)return new ArrayList<Integer>();int num = rowIndex+1;List<Integer> list = new ArrayList<Integer>(num);double [] factor = new double[num];double result = 1;factor[0] = 1;list.add(1);for(int i=1; i<num ; i++){result = result*(num-i)/i;factor[i] = result;list.add((int)factor[i]);}return list;}

版權聲明：本文博主原創文章，博客，未經同意不得轉載。