LeetCode118:杨辉三角
解析:
杨辉三角应该是比较熟悉的题目,可以看成是一个二维数组,数组的每一行元素个数比上一行多一个,每一行第一个元素和最后一个元素都是1,其余元素,是它左上角元素和它上面的元素之和。用公式表示就是f[m][n]=f[m-1][n-1]+f[m-1][n],前提是m->=0,n-1>=0 ; 所以根据这个公式就可以很好计算了。
用程序的话,就是需要一个vector保存每一行的值,需要一个vector<vector<int>>保存最终结果。
代码:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result;
if (numRows == 0) return result;
vector<int> tmp;//用来保存每一行的值
tmp.push_back(1);
result.push_back(tmp);//先把第一行加入到结果中去
if (numRows == 1) {//如果只有一行
return result;
}
for (int i = 2; i <= numRows; i++) {
vector<int> tmp(i, 1);
for (int j = 1; j<i - 1; j++) {
tmp[j] = result[i - 2][j - 1] + result[i - 2][j];//计算公式
}
result.push_back(tmp);
}
return result;
}