Problem: 118. 杨辉三角
解析
利用杨辉三角特性，每一行的第一个和最后一个元素都是1，中间元素等于上一行的前一个元素和当前元素之和。
朴素动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
vector<int> resPart;
vector<int> DP(numRows);
DP[0] = 1;
vector<int> temp;
for (int i = 0; i < numRows; ++i) {
resPart.push_back(1);
temp = DP;
for (int j = 1; j <= i; ++j) {
temp[j] = DP[j - 1] + DP[j];
resPart.push_back(temp[j]);
}
DP = temp;
res.push_back(resPart);
resPart.clear();
}
return res;
}
};
|
简化
可去掉中间的暂存值简化代码为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
for (int i = 0; i < numRows; ++i) {
vector<int> temp(i + 1, 1);
for (int j = 1; j < i; ++j) {
temp[j] = res[i - 1][j - 1] + res[i - 1][j];
}
res.push_back(temp);
}
return res;
}
};
|
进一步优化
甚至可以开始给res numRows的空间，用res[i].resize(i+1)把中间的temp数组去掉，懒得搞了
