LeetCode119 Pascal's Triangle II

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论