杨辉三角

描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/pascals-triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

使用动态规划来解决 Pascal’s Triangle 问题可以更加高效地生成 Pascal’s Triangle。具体来说，我们可以使用一个二维数组 dp 来存储 Pascal’s Triangle，其中 dp[i][j] 表示 Pascal’s Triangle 中第 i 行第 j 列的数字。根据 Pascal’s Triangle 的定义，我们可以得到以下递推式：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

其中，dp[i-1][j-1] 表示上一行的左上角数字，dp[i-1][j] 表示上一行的右上角数字。我们可以根据这个递推式来填充 dp 数组，最后返回 dp 数组即可。

以下是使用动态规划来解决 Pascal’s Triangle 问题的代码：

C++代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        // 创建一个二维数组，用于存储 Pascal's Triangle
        vector<vector<int>> dp(numRows);
        
        // 遍历每一行
        for (int i = 0; i < numRows; i++) {
            // 在当前行中创建一个一维向量，用于存储该行的数字
            vector<int> row(i+1);
            
            // 在每一行的开头和结尾设置为1
            row[0] = row[i] = 1;
            
            // 遍历当前行中除了开头和结尾以外的数字
            for (int j = 1; j < i; j++) {
                // 当前行的数字由上一行对应位置的数字相加得到
                row[j] = dp[i-1][j-1] + dp[i-1][j];
            }
            
            // 将当前行添加到 Pascal's Triangle 中
            dp[i] = row;
        }
        
        // 返回 Pascal's Triangle
        return dp;
    }
};