当前位置：网站首页>LeetCode 0118. 杨辉三角

LeetCode 0118. 杨辉三角

2022-07-17 17:15:00 【Tisfy】

【LetMeFly】118.杨辉三角

力扣题目链接：https://leetcode.cn/problems/pascals-triangle/

给定一个非负整数 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 <= numRows <= 30

方法一：动态规划

我们用vector<vector<int>> ans来存放杨辉三角。

初始化杨辉三角的第一行（ans.push_back({1})）

之后从第 $2$ 行开始（下标 $i$ 从 $1$ 开始），不断生成每一行。

第i + 1行的生成方法为：

首先向这一行中添加第一个元素 $1$ （ans.push_back({1})）

然后从第 $2$ 个元素开始（下标 $j$ 从 $1$ 开始），到这一行最后一个元素的前一个为止，第i + 1行的第j + 1个元素等于上一行的对应两个元素之和（ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]）

最后，再向这一行的末尾添加一个 $1$ 即可。

如果不理解，可以参考杨辉三角的第 $3$ 行的第 $2$ 个元素 $3$ 的生成来研究：

当计算到第 $3$ 行的第 $2$ 个元素时， $i = 2, j = 1$ 。此时 $an s [i] [j] = an s [i - 1] [j - 1] + an s [i - 1] [j] = 1 + 1 = 2$ ，说明第 $3$ 行的第 $2$ 个元素的值为 $2$ 。

1+1

时间复杂度 $O(size^2)$
空间复杂度 $O (1)$ ，答案不计入算法空间复杂度

AC代码

C++

class Solution {
    
public:
    vector<vector<int>> generate(int numRows) {
    
        vector<vector<int>> ans;
        ans.push_back({
    1});
        for (int i = 1; i < numRows; i++) {
    
            ans.push_back({
    1});
            for (int j = 1; j < i; j++) {
    
                ans[i].push_back(ans[i - 1][j - 1] + ans[i - 1][j]);
            }
            ans[i].push_back(1);
        }
        return ans;
    }
};