当前位置：首页 > article >正文

LeetCode 热题 100_杨辉三角（82_118_简单_C++）(动态规划)

article 2025/4/1 17:36:16

LeetCode 热题 100_杨辉三角（82_118）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（动态规划）：
  - 代码实现
  - - 代码实现（思路一（动态规划））：
    - 以思路一为例进行调试

题目描述：

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

题解：

解题思路：

思路一（动态规划）：

1、我们可以将数据使其左对齐，则第一列和对角线上的元素为1。其余位置为左上方元素+正上方元素。
请添加图片描述
2、具体思路如下：
① 可以使用二维动态数组来存储答案，第一行含有一个元素，第二行含有2个元素，以此类推。
② 可以将每行的元素初始值赋值为1，每行左右两端的初始值1不变，中间的元素由左上方元素+正上方元素得出。

2、复杂度分析：
① 时间复杂度：numRows²，生成「杨辉三角」的前 numRows 行。
② 空间复杂度：O(1)。不考虑返回值的空间占用。

代码实现

代码实现（思路一（动态规划））：

class Solution {
public:
    // generate 函数用来生成杨辉三角的前 numRows 行
    vector<vector<int>> generate(int numRows) {
        // 创建一个二维数组 ans，大小为 numRows，每行的大小根据需要动态调整
        vector<vector<int>> ans(numRows);
        
        // 遍历每一行（从 0 到 numRows - 1）
        for (int i = 0; i < numRows; i++){
            // 为当前行调整大小，并初始化为全1
            // 每行的元素个数是 i+1，所以这行的元素数量为 i+1
            ans[i].resize(i+1, 1);
            
            // 从第二行开始，计算每一行中非边界的元素值
            // 这些元素的值等于上一行的左右两个元素之和
            for (int j = 1; j < i; j++){
                ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
            }
        }
        
        // 返回最终生成的杨辉三角
        return ans;
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    // generate 函数用来生成杨辉三角的前 numRows 行
    vector<vector<int>> generate(int numRows) {
        // 创建一个二维数组 ans，大小为 numRows，每行的大小根据需要动态调整
        vector<vector<int>> ans(numRows);
        
        // 遍历每一行（从 0 到 numRows - 1）
        for (int i = 0; i < numRows; i++){
            // 为当前行调整大小，并初始化为全1
            // 每行的元素个数是 i+1，所以这行的元素数量为 i+1
            ans[i].resize(i+1, 1);
            
            // 从第二行开始，计算每一行中非边界的元素值
            // 这些元素的值等于上一行的左右两个元素之和
            for (int j = 1; j < i; j++){
                ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
            }
        }
        
        // 返回最终生成的杨辉三角
        return ans;
    }
};

int main(){
    int n=10;
    Solution s;
    vector<vector<int>> ans= s.generate(n);
    for(const auto &row:ans){
        for(const auto &i:row){
            cout<<i<<" ";
        }
        cout<<endl;

    }
    return 0;
}