# 杨辉三角——数组、动态规划

> 发布于：2022-03-10 | 分类：刷题 | 原文：https://www.imbailey.cn/post/pascals-triangle-array-dynamic-programming

## 题目

> 本题来自：https://leetcode-cn.com/problems/pascals-triangle/

#### [118. 杨辉三角]

难度简单708收藏分享切换为英文接收动态反馈

给定一个非负整数 *`numRows`，*生成「杨辉三角」的前 *`numRows`* 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

![img](https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/1626927345-DZmfxB-PascalTriangleAnimated2.gif)

 

**示例 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`



## 题解

找规律，第`i`行第`j`个数等于第`i-1`行第`j-1`个数加第`i-1`行第`j`个数，即`res[i][j]=res[i-1][j-1]+res[i][j]`。

一开始我弄错一个变量，导致数组越界，找了半天都没找出来，我还以为是c++的问题，就换了python写，python的报错比较友好，终于让我发现了错误的地方。

所以python代码：

```python
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[] for i in range(0,numRows)]
        res[0].append(1)
        if numRows==1:
            return res;
        for i in range(1,numRows):
            for j in range(0,i+1):
                if j==0 or j==i:
                    res[i].append(1)
                else:
                    # print(i,res)
                    res[i].append(res[i-1][j-1]+res[i-1][j])
        return res
```

c艹代码：

```c++
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        res[0].push_back(1);
        if(numRows==1){ 
            return res;
        }
        for(int i=1;i<numRows;i++){
            for(int j=0;j<i+1;j++){
                if(j==0 || j==i){
                    res[i].push_back(1);
                }
                else{
                    res[i].push_back(res[i-1][j-1]+res[i-1][j]);
                }
            }
        }
    return res;
    }
};
```