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

题目

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

[118. 杨辉三角]

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

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

题解

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

一开始我弄错一个变量，导致数组越界，找了半天都没找出来，我还以为是c++的问题，就换了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艹代码：

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;
    }
};