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

思路：每个数都由左上方和右上方的数相加得到:
  $dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$
加上判断边界条件，当 j = 0 || j == i 时，dp[i][j] = 1;

// 实现一
vector<vector<int>> generate(int numRows) {
    vector<vector<int>> dp(numRows);
    dp[0].push_back(1);
    for (int i = 1; i < numRows; ++i) {
        for (int j = 0; j <= i; ++j) {
            int tmp = 0;
            if (j == 0 || j == i) {
                dp[i].push_back(1);
            } else {
                dp[i].push_back(dp[i - 1][j] + dp[i - 1][j - 1]);
            }
        }
    }
    return dp;
}
 
// 实现二
vector<vector<int>> generate(int numRows) {
    vector<vector<int>> dp(numRows);
    dp[0].push_back(1);
    for (int i = 1; i < numRows; ++i) {
        for (int j = 0; j <= i; ++j) {
            int tmp = 0;
            if (j > 0) {
                tmp += dp[i - 1][j - 1];
            }
            if (j < i) {
                tmp += dp[i - 1][j];
            }
            dp[i].push_back(tmp);
        }
    }
    return dp;
}