一. 題目描述
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
二. 題目分析
關於帕斯卡三角形的定義,可參考:http://baike.baidu.com/link?url=qk_-urYQnO4v6v3P4BuMtCa0tMNUqJUk4lmbkb1aqbqikBU-ndiMlTF20fq2QUjTTFTeTohZ72KFxgBnz4sJha
將該三角形的左邊對齊,就能夠發現,tri[i][j] = tri[i-1][j-1] + tri[i-1][j]
。因此這裡的代碼並沒有什麼技巧。
三. 示例代碼
class Solution {
public:
vector> generate(int numRows) {
vector> result;
if (numRows <= 0)
return result;
else
{
vector temp(1, 1);
result.push_back(temp);
if (numRows == 1) return result;
temp.push_back(1);
result.push_back(temp);
if (numRows == 2) return result;
for (int i = 2; i < numRows; ++i)
{
vector temp(i + 1, 1);
for (int j = 1; j < i; ++j)
temp[j] = result[i - 1][j - 1] + result[i - 1][j];
result.push_back(temp);
}
}
return result;
}
};