给定一个非负整数 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]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //二维数组初始化
        vector<vector<int>> ret(numRows);//定义numRows行二维数组,每行元素为空
        for(int i=0;i<numRows;i++){
            ret[i]=vector<int>(i+1,1);//每行i+1个元素,初始化为1
        }
        /* 也可以这样初始化
        vector<vector<int>> ret;
        for(int i = 0; i < numRows; ++i) {
                ret.push_back(vector<int>(i + 1, 1));
        }
        */
        for(int i=0;i<numRows;i++){
            for(int j=1;j<i;j++){//第0行和第i行为1,j的范围从1到i-1
                ret[i][j]=ret[i-1][j-1]+ret[i-1][j];  
            }
        }
        return ret;
    }
};

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部