我们都知道一个结论：组合数当n,m都很小的时候可以利用杨辉三角直接求
那么为什么呢？
组合数：
我们高中学到的组合数：
CnmC^m_nCnm:从n个物品里面找出m个物品所有的方案*
Cnm=n!m!(n−m)!C^m_n=\frac{n!}{m!(n-m)!}Cnm=m!(n−m)!n!
杨辉三角：
杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年----百度
像这样
这样
那么这东西为什么会和组合数有关系呢？
当我用DP的思想：
Cnm=从n个物品中选择m个物品有多少种选法C^m_n=从n个物品中选择m个物品有多少种选法Cnm=从n个物品中选择m个物品有多少种选法
对应的动态转移：
f[i][j]=f[i−1][j−1]+f[i−1][j]f[i][j]=f[i - 1][j - 1] + f[i - 1][j]f[i][j]=f[i−1][j−1]+f[i−1][j]
#include
using namespace std;
int f[101][101];
int main()
{
f[0][0] = 1;
for(int i = 1; i <= 6; i ++)
for(int j = 0; j < i; j ++)
f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
for(int i = 1; i <= 6; i ++)
{
for(int j = 0; j < i; j ++)
cout << f[i][j] << " ";
cout << endl;
}
return 0;
}
运行出来的结果让我震惊了
刚好就是杨辉三角
从这个角度正好解释了他们俩的关系
其实这时候想想杨辉三角的值就是等于它肩膀上两个值的和
刚好对应f[i][j]=f[i−1][j−1]+f[i−1][j]f[i][j]=f[i - 1][j - 1] + f[i - 1][j]f[i][j]=f[i−1][j−1]+f[i−1][j]