PascalsTriangle

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution

模拟题, 求杨辉三角(欧洲叫帕斯卡三角形), 依次迭代即可

vector<vector<int>> generate(int n) {
	vector<vector<int>> result;
	for (int i = 0; i < n; ++i) {
		result.push_back(vector<int>(i + 1, 0));
		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;
}

扩展

Pascal's Triangle II, 打印指定行，使用O(k)空间，k为行数

关于杨辉三角

                           1
                         1   1   
                       1   2   1   
                     1   3   3   1   
                   1   4   6   4   1   
                 1   5   10  10  5   1   
               1   6   15  20  15  6   1   
             1   7   21  35  35  21  7   1   
           1   8   28  56  70  56  28  8   1   
         1   9   36  84  126 126 84  36  9   1   
       1   10  45  120 210 252 210 120 45  10  1   
     1   11  55  165 330 462 462 330 165 55  11  1    
   1   12  66  220 495 792 924 792 495 220 66  12  1
...
1, C(n,1), C(n,2), …, C(n,n-1), C(n,n)

基本性质:

1. 每个数等于它上方两数之和。
2. 每行数字左右对称，由1开始逐渐变大。
3. 第n行的数字有n项。
4. 第n行数字和为2^n-1。
5. 第n行的m个数可表示为 C(n-1,m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
6. 第n行的第m个数和第n-m+1个数相等 ，为组合数性质之一。
7. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。
8. (a+b)ⁿ的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项.
9. 将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数；将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。
10. 将各行数字相排列，可得11的n-1（n为行数）次方：1=11^0; 11=11^1; 121=11^2……当n≥5时会不符合这一条性质，此时应把第n行的最右面的数字"1"放在个位，然后把左面的一个数字的个位对齐到十位... ...，以此类推，把空位用“0”补齐，然后把所有的数加起来，得到的数正好是11的n-1次方。以n=11为例，第十一行的数为：1,10,45,120,210,252,210,120,45,10,1，结果为 25937424601=11¹⁰。
11. 二项式定理，第3行的三个数是两个数和的平方的每一项系数，即(a + b)² = a² + 2ab + b², 同理第4行对应(a + b)³的系数.
12. 除了1以外，所有正整数出现有限次，只有2刚好出现一次。还未找到刚好出现5次的数.

如何求第n行的数(假设n从0开始计数):

当然可以直接求组合C(n,k)， 当求组合比较麻烦。

可以使用迭代的方式求：后面的一个数等于前面的数乘以一个分数,这个分数从左到右分别为n/1, (n-1)/2, ..., 2/(n-1), 1/n

比如求第5行:

• 初始化第一项为1
• 分数从左到右为5/1, 4/2， 3/3, 2/4, 1/5， 因此从左到右的数字为1 * 5/1 == 5, 5 * 4/2 == 10, 10 * 3/3 = 10, 10 * 2/4 == 5, 5 * 1/5 == 1, 最后结果为1,5,10,10,5,1

实现见Pascal's Triangle II