# Pascal's Triangle II

Given a non-negative index k where k≤ 33, return the _k_th index row of the Pascal's triangle.

Note that the row index starts from 0.

Example:

``````Input:
3

Output:
[1,3,3,1]``````

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

## Analysis

Dynamic Programming

Same as Pascal's Triangle I, just need to use current row and previous row in order to get O(k) space complexity.

Math

row `k` of Pascal's Triangle:

`[C(k,0), C(k,1), ..., C(k, k-1), C(k, k)]`

and

`C[k,i] = C[k,i-1]*(k-i+1)/i`

## Solution

O(K) space O(K^2) time (3ms 11.27%) - 在首位加`1`，内层循环正序即可

``````class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
for (int i = 0; i <= rowIndex; i++) {
for (int j = 1; j < i; j++) {
row.set(j, row.get(j) + row.get(j + 1));
}
}
return row;
}
}``````

Same approach - Another One 在末尾加`1`， 内层循环要从末尾倒序循环

``````class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i <= rowIndex; i++) {
for (int j = i - 1; j >= 1; j++) {
res.set(j, res.get(j - 1) + res.get(j));
}
}
return res;
}
}``````

O(K) space and O(K) time using Math (1ms 91.55%)

``````class Solution {
public List<Integer> getRow(int rowIndex) {
Integer[] rowList = new Integer[rowIndex+1];
rowList[0] = 1;
for(int i=1; i<rowList.length;i++) {
rowList[i] = (int)((long)rowList[i-1]*(rowIndex-(i-1))/(i));
}
return Arrays.asList(rowList);
}
}``````

O(K) space and O(K^2) (0ms 100%)

``````class Solution {
public List<Integer> getRow(int rowIndex) {
int[] res = new int[rowIndex+1];
res[0] = 1;
for(int i=1; i<rowIndex+1; i++)
for(int j=i; j>=1; j--)
res[j] += res[j-1];
List<Integer> list = new ArrayList<> ();
for(int n : res) {
}
return list;
}
}``````

Traditional 2D DP - storing dp[][] element for each layer - O(n^2) time, and O(n^2) space - (1ms AC)

``````class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> ans = new ArrayList<>();
int[][] dp = new int[rowIndex + 1][rowIndex + 1];
dp[0][0] = 1;
for (int i = 1; i <= rowIndex; i++) {
dp[i][0] = 1;
dp[i][i] = 1;
for (int j = 1; j < i; j++) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}
}
for (int k = 0; k <= rowIndex; k++) {