题目链接
Leetcode.118 杨辉三角
easy
题目描述
给定一个非负整数 n u m R o w s numRows numRows,生成「杨辉三角」的前 n u m R o w s numRows numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
- 1 ≤ n u m R o w s ≤ 30 1 \leq numRows \leq 30 1≤numRows≤30
解法:动态规划
在 杨辉三角 中,每一行比前一行多一个元素;
在每一行中,第一个元素和最后一个元素都是 1 1 1;
我们用 f [ i ] [ j ] f[i][j] f[i][j] 表示第 i i i 行的,下标为 j j j 的元素:
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j ] f[i][j] = f[i - 1][j-1] + f[i-1][j] f[i][j]=f[i−1][j−1]+f[i−1][j]
时间复杂度: O ( n 2 ) O(n^2) O(n2)
C++代码:
class Solution {
public:vector<vector<int>> generate(int n) {vector<vector<int>> f{{1}};for(int len = 2;len <= n;len++){vector<int> temp;int i = len - 1;for(int j = 0;j < len;j++){if(j == 0 || j == len - 1) temp.push_back(1);else{temp.push_back(f[i - 1][j - 1] + f[i - 1][j]);}}f.push_back(temp);}return f;}
};