Posted on 2014-01-11 02:46
Uriel 閱讀(115)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
兩題楊輝三角形的題
Pascal's Triangle：求前n行
1 class Solution {
2 public:
3 vector<vector<int> > generate(int numRows) {
4 int dp[2][10010];
5 vector<vector<int> > res;
6 for(int i = 1; i <= numRows; ++i) {
7 vector<int> tp;
8 for(int j = 1; j <= i; ++j) {
9 if(j == 1 || j == i) dp[i & 1][j] = 1;
10 else
11 dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
12 tp.push_back(dp[i & 1][j]);
13 }
14 res.push_back(tp);
15 }
16 return res;
17 }
18 };
Pascal's Triangle II：求第k行
1 class Solution {
2 public:
3 vector<int> getRow(int rowIndex) {
4 int dp[2][10010];
5 vector<int> res;
6 for(int i = 1; i <= rowIndex + 1; ++i) {
7 for(int j = 1; j <= i; ++j) {
8 if(j == 1 || j == i) dp[i & 1][j] = 1;
9 else
10 dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
11 if(i == rowIndex + 1) res.push_back(dp[i & 1][j]);
12 }
13 }
14 return res;
15 }
16 };