数论

我们都知道一个结论：组合数当n,m都很小的时候可以利用杨辉三角直接求

那么为什么呢？

组合数：

我们高中学到的组合数：

C n m C^m_n Cnm​:从n个物品里面找出m个物品所有的方案* C n m = n ! m ! ( n − m ) ! C^m_n=\frac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​

杨辉三角： 杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年----百度

像这样 这样

那么这东西为什么会和组合数有关系呢？ 当我用DP的思想： C n m = 从 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]