早在11世纪，北宋数学家贾宪发明了上图这个三角形以及增乘方造表法，可以求任意高次方的展开式系数。
200年后，南宋数学家杨辉在《详解九章算术》里解释这种形式的数表，并说明此表引自贾宪的《释锁算术》。杨辉引用贾宪的三角表图和文字描写，至今仍保存在大英博物馆所藏《永乐大典》中。因《释锁算术》早已失传，除杨辉这个人证之外，贾宪的发明权还缺少物证，故一般国内著作多称此三角为杨辉三角。期待更多的考古发现能为贾宪提供证明。而西方发现这个三角已经是300多年后了。17世纪的帕斯卡将杨辉三角用于解决一些概率论上的问题，影响广泛故西方称之为帕斯卡三角。
杨辉三角的作法非常简单，第1行一个数字1，第2行两个数字1，接下来每一行，除最左侧和最右侧仍为1之外，其余的数字为其左上角与右上角数字之和。
杨辉三角的用途非常广泛，最著名的用途是用于二项式展开。因为杨辉三角上的每一个数字都和二项式展开的系数有对应的关系，见下图：
杨辉三角与概率论中的组合数也有对应关系， 见下图：
由于组合数计算公式复杂（见上图，需用到阶乘运算），在信奥赛中，通过杨辉三角计算组合数是经常用到的方法。
NOIP2002有一道非常著名的递推题《马踏过河卒》，小卒在左上角A点，要走到右下角B点，小卒只能往下或者往右走，如果不考虑被马吃掉，共有几种走到B点的方法？
答案可查下表，而这张表，顺时针转个方向，就是杨辉三角：
杨辉三角看起来像是一堆排列整齐的数字，但实际上它是一个数学宝库，它充满了模式和秘密，有些秘密非常的神奇而难以琢磨，甚至有人猜测整个宇宙的奥秘是不是藏在了杨辉三角里，我们一起来看一下吧：
【秘密一】数字2的幂
【秘密二】暗藏三角形数
【秘密三】暗藏完全平方数
【秘密四】暗藏数字11
最后几行似乎和11的幂对不上，其实是因为挤在一起了，请看下图：
【秘密五】暗藏斐波那契数列
斐波那契数列里暗藏黄金分割，号称是在DNA中，自然界，甚至整个银河系都随处可见。
【秘密六】暗藏卡特兰数
卡特兰数由凸多边形三角划分得出，见下图：
在信奥赛中，卡特兰数常用于出栈序列的计算上，也不知道为啥它也会藏在杨辉三角里。
【秘密七】质数是主宰
我们发现但凡每一行的第2个数字是质数的话(见红圈内数字），其后所有的数字，均为这个质数的倍数（1除外）。
【秘密八】隐藏了无数根曲棍球棒
从任意一个数字1出发，沿一个方向走随便走多远，然后突然拐向另一个方向，新方向上那个数字，是所有之前获得的数字之和。
【秘密九】隐藏谢尔宾斯基三角形
当我们把杨辉三角中所有的奇数涂成黑色，一个神奇的图案出现了，这个三角形，被称之为谢尔宾斯基（Sierpinski triangle）三角形，而这个三角形，似乎和埃及金字塔有着千丝万缕的联系，后者据说隐藏着来自宇宙的神秘力量。我们来看看下图，这是即将在明年开放的埃及大博物馆的效果图，细思极恐，有没有？
接下来，我们写一个程序来生成杨辉三角吧。
杨辉三角是一个等腰三角形，如果要在屏幕上画出等腰三角形，每个元素的定位有些困难。需要较复杂的定位计算，简单点，就生成一个完全靠左墙贴合排列的杨辉三角形吧，如下图：
整个完整的题目如下（摘自洛谷P5732）：
由于输入的n的值域仅为[0, 20]， 非常小，开个25行25列的二维数组来存放整个杨辉三角即可。根据杨辉三角的计算方法，除1以外的每个值，为其左上方和右上方两值之和。但如果靠左墙排列，则每个值为其左上方和正上方两值之和，见下图：
为了计算方便，整个杨辉三角在数组里存放的位置下降1行，右移一列，使第1行保持全0，第1列保持全0。这样整个杨辉三角的计算都可以使用如下的递推公式（即使那些1的生成），而不用担心出现a[-1][0]之类的越界现象，我们把这第1行第1列称为哨兵，是防止数组越界的一种小技巧：
对于递推填表题，除了找到递推公式，还要注意填表的边界初始值和填表的顺序。在本题中，我们要把第1行第1列填数字1，否则整个杨辉三角在递推作用下，也全部会填成0。至于填表的顺序，可以自上而下，自左而右，用双重循环实现。
整个程序如下，每计算出一个值，就直接输出即可：
在实际比赛中，输入的n值，可能会非常大，大到整个二维数组在限定的内存空间中存放不下（有时规定可用内存仅512M），这样就会产生MLE错误（Memory Limit Exceeded)。于是要对内存的使用进行优化。观察递推式，发现每填写一个单元时，只关注其上一行的两个单元，而再往上所有行都已经用不上，浪费内存可耻！因此可以用滚动数组来进行空间复杂度优化。滚动数组只需要开两行即可。代码如下：
还可以进一步的优化，现在的填表顺序是自上往下，自左往右。如果我们变化一下填表顺序，改成自上往下，自右往左呢？当我们填写第i行第j列这个单元时，需要用到上一行的当前列和前一列，如果我把滚动数组a[flag][j]降为一维数组，去掉滚动索引，自右往左填表时，a[j]在未更新时，记录的就是上一行的第j列的值，a[j - 1]记录的就是上一行第j - 1列的值。因此我可以直接用a[j] = a[j] + a[j - 1]来更新当前行第j列的值。而且还可以立即就输出，因为整个杨辉三角是左右对称的，左侧第x个值和右侧第x个值并无不同，利用上这个对称特性，代码就变得非常简单了，如下所示：
这个代码简化的方法，也经常被用在动态规划算法中的01背包问题和完全背包问题的空间复杂度优化之中。