杨辉三角

题面

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

分析

• 代码实现

  class Solution {
  public:
      vector<vector<int>> generate(int numRows) {
          vector<vector<int>> res;
          res.push_back(vector(1, 1));
          for (int i = 1; i < numRows; i++) {
              vector<int> row = vector(i + 1, 0);
              for (int j = 0; j <= i; j++) {
                  int left = j - 1 < 0 ? 0 : res[i - 1][j - 1];
                  int right = j >= i ? 0 : res[i - 1][j];
                  row[j] = left + right;
              }
              res.push_back(row);
          }
          return res;
      }
  };

• 如何理解杨辉三角的递推式？

• 递推式

  $$c[i][j] = c[i-1][j-1] + c[i-1][j]$$

• 本质上是一个组合数恒等式，其中 $c[i][j]$ 表示从 $i$ 个不同物品中选出 $j$ 个物品的方案数

• 如何理解上式呢？考虑其中某个物品选或不选：

  • 选：问题变成从剩下 $i-1$ 个不同物品中选出 $j-1$ 个物品的方案数，即 $c[i-1][j-1]$
  • 不选：问题变成从剩下 $i-1$ 个不同物品中选出 $j$ 个物品的方案数，即 $c[i-1][j]$

• 二者相加（加法原理），得

  $$c[i][j] = c[i-1][j-1] + c[i-1][j]$$