计算排列组合C(n k)

通过归纳法可得：C(n,k)=C(n-1,k-1)+C(n-1,k)

所以通过数组填表可以得到一个表格，其值代表组合数。

//计算排列组合C(n,k)=C(n-1,k-1)+C(n-1,k)int c[15][15] = { 0 };void init(){c[0][0] = 1;for (int i = 1; i < 15; ++i){c[i][0] = 1;for (int j = 1; j < 15; ++j){c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}}}

c数组输出如下 (也是一个杨辉三角):

由于当n的值太大时，数组的值会超出int甚至long long，此时可以进行求模运算来避免这种越界。

题目来源于腾讯秋招：小Q的歌单。

同时此题还是一个0-1背包问题，可以通过动态规划填表解决。