HHot 100C++ 图解

118. 杨辉三角

简单 动态规划(一维) 3 帧动画 在力扣上做

一句话套路tri[i][j]=上一行相邻两数之和

题目描述

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

思路

时间O(n^2)
空间O(n^2)(输出本身)

状态

tri[i][j] = tri[i-1][j-1] + tri[i-1][j],边界每行首尾为 1。

变体

Q119 只返回第 rowIndex 行 -> 逆序原地滚动成一行,空间 O(k);

另一个视角

第 n 行第 k 个数就是组合数 C(n, k)。

图解

1 0 1 2 3 4 1 1 1 2 1 1 3 3 1 1 4 6 4 1 每行首尾为 1,中间的 = 上一行相邻两个之和。
第 k 行第 j 个数 = C(k,j)。从上一行递推即可。

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp13 行
namespace lc0118 {
class Solution {
 public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> tri(numRows);
    for (int i = 0; i < numRows; ++i) {
      tri[i].assign(i + 1, 1);  // 每行首尾都是 1
      for (int j = 1; j < i; ++j) tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
    }
    return tri;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q118_pascals_triangle5 行
lc0118::Solution s;
CHECK_EQ(s.generate(5),
         vector<vector<int>>({{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1}}));
CHECK_EQ(s.generate(1), vector<vector<int>>({{1}}));
CHECK_EQ(s.generate(3)[2], vector<int>({1, 2, 1}));

↑↓ 选择↵ 打开/ 随时唤起