LeetCode119 Pascal's Triangle II


描述

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

样例

1
2
Input:
k = 3
1
2
Output:
[1,3,3,1]

思路

求第$k$层的帕斯卡三角。

一种方法是像LeetCode118 Pascal’s Triangle那样,先把$k$层全求出来,然后再取出第$k$层,这样空间是$\mathcal{O}(k^2)$。

为了降低空间复杂度,可以考虑使用滚动数组。

观察下列的递推式,

假设我们忽略第一维的信息,只利用$dp[j] = dp[j] + dp[j-1]$来更新,是否可以呢?

答案是可以的,但是需要注意更新的顺序。

在有两维的时候,$j$按什么顺序更新都没问题,但是在只有一维的情况下,$j$只能从大往小更新。

当$j$从大往小更新的时候,等号左边的$dp[j]$ 指代$dp[i][j]$,等号右边的$dp[j]$指代$dp[i-1][j]$,$dp[j-1]$指代$dp[i-1][j-1]$,这样才能保证更新的时候等号右边的数据还是上一层的。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> dp(rowIndex + 1, 0);
dp[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
for (int j = i; j >= 1; --j) dp[j] += dp[j-1];
}
return dp;
}
};