基于二维递推的杨辉三角计算组合数

组合数问题解析

从n个不同的物件中挑选出m个，存在多少种不同的选取方式

杨辉三角的数学内涵与应用

第i行第j列所对应的数值，表示从i个不同物品中选取j个时，能够形成的不同组合方式的数量（行与列的编号均以0为起始点）。

当高度为5时（此时下标最大可取至i = 4，j = 4），杨辉三角的结构如下：

思路

当前我们需要计算从i个物品中选取j个的组合方式数目，记作f[i][j]。针对第一个物品，存在两种处理方式：将其纳入选择范围，或排除在选择之外：

1. 将第一个物品纳入选择范围：由于该物品已被选定，因此还需从剩下的i-1个物品中挑选j-1个，对应的组合方式数目为 f[i-1][j-1]。
2. 将第一个物品排除在选择范围之外：此时需要从余下的i-1个物品中选出j个，对应的组合方式数目为 f[i-1][j]。

由此可得递推关系式为：f[i][j] = f[i-1][j-1] + f[i-1][j]。

边界条件

1. 对于所有i，f[i][0] = 1，即第一列的所有值均为1；