【LeetCode】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

题解

f(i,0) = f(i,i) = 1
f(i,j) = f(i-1,j-1)+f(i-1,j)

class Solution {
    
public:
    vector<vector<int>> generate(int numRows) {
    
        vector<vector<int>> result;
        for(int i=0;i<numRows;i++)
        {
    
            vector<int> tmp(i+1);
            tmp[0] = tmp[i] = 1;
            for(int j=1;j<i;j++)
            {
    
                tmp[j] = result[i-1][j-1]+result[i-1][j];
            }
            result.push_back(tmp);
        }
        return result;
    }
};


//改良
class Solution {
    
public:
    vector<vector<int>> generate(int numRows) {
    
        vector<vector<int>> result(numRows);
        for(int i=0;i<numRows;i++)
        {
    
            result[i].resize(i+1);
            result[i][0] = result[i][i] = 1;
            for(int j=1;j<i;j++)
            {
    
                result[i][j] = result[i-1][j-1]+result[i-1][j];
            }
        }
        return result;
    }
};

阶乘法
i,j从0开始编号，则f(i,j) = C(j,i)
例：C(2,4) = 6, C(1,4) = 4

略