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)的空间复杂度。下面先上O(k^2)的算法。
@Test
public List<Integer> getRow(int rowIndex) {
int[][] f = new int[rowIndex + 1][rowIndex + 1];
List<Integer> res = new ArrayList<>();
for (int i = 0; i <= rowIndex; i++) {
res.add(getNum(rowIndex, i, f));
}
return res;
} public int getNum(int row, int col, int[][] f) {
if (row == 0 || row == 1 || col == 0 || col == row)
return 1;
if (col < 0)
return 0;
if (f[row][col] == 0)
f[row][col] = getNum(row - 1, col, f) + getNum(row - 1, col - 1, f);
return f[row][col];
}
上面算法还算比较直观，就是依次取出第rowIndex行的各个元素，加入到list中。通过代码可以发现，第K行的数据仅仅依赖于第K-1行，也就是说，我们可以进行降维，将二维数组降为一维，这里注意，降维之后，用一维数组来记录当前行的数据，计算的时候应从后往前计算，还是以二维进行假设，当前元素为
F[k][col]=F[k-1][col]+F[k-1][col-1]
那么，当循环走完k-1遍时，一维数组里的数据F[col]里存的是对应二维数组的F[k-1][col]，从后往前计算，F[col]=F[col]+F[col-1]，那么走完这一遍，F数组里存的是F[k][0...col]的数据，如果从前往后计算，F[col]=F[col]+F[col-1]，仔细看，F[col+1]=F[col+1]+F[col]，这里就有问题了，F[col]这里已经不是k-1状态的数据了，所以这样计算有问题。这个降维的技巧在动态规划里也经常用，注意要从后往前计算。
Talk is cheap。
public ArrayList<Integer> getRow(int rowIndex) {
ArrayList<Integer> res = new ArrayList<>();
if (rowIndex < 0)
return res;
res.add(1);
for (int i = 1; i <= rowIndex; i++) {
for (int j = res.size() - 2; j >= 0; j--) {
res.set(j + 1, res.get(j) + res.get(j + 1));
}
res.add(1);
}
return res;
}