两种方法都会节省时间，但第一种方法很容易出现整数溢出。
方法一：
这种方法将在最短的时间内（最多n/2迭代）产生结果，并且可以通过仔细进行乘法来减少溢出的可能性：
long long C(int n, int r) {
if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
long long ans = 1;
int i;
for(i = 1; i <= r; i++) {
ans *= n - r + i;
ans /= i;
}
return ans;
}
此代码将从较小的一端开始乘分子，并且由于任何k连续整数的乘积都可以被 整除k!，因此不会有可除性问题。但是溢出的可能性仍然存在，另一个有用的技巧可能是在进行乘法和除法之前除以它们的 GCD（并且n - r + i仍然可能发生溢出）。i
方法二：
在这种方法中，您实际上将构建帕斯卡三角。动态方法比递归方法快得多（第一个是指数的O(n^2)，而另一个是指数的）。但是，您也需要使用O(n^2)内存。
# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];
void makeTriangle() {
int i, j;
// initialize the first row
triangle[0][0] = 1; // C(0, 0) = 1
for(i = 1; i < MAX; i++) {
triangle[i][0] = 1; // C(i, 0) = 1
for(j = 1; j <= i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
}
long long C(int n, int r) {
return triangle[n][r];
}
然后，您可以随时查找C(n, r)。O(1)
如果您需要特定的C(n, r)（即不需要完整的三角形），则可以O(n)通过从上到下覆盖三角形的同一行来消耗内存。
# define MAX 100
long long row[MAX + 1];
int C(int n, int r) {
int i, j;
// initialize by the first row
row[0] = 1; // this is the value of C(0, 0)
for(i = 1; i <= n; i++) {
for(j = i; j > 0; j--) {
// from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
row[j] += row[j - 1];
}
}
return row[r];
}
内循环从头开始，以简化计算。如果从索引 0 开始，则需要另一个变量来存储被覆盖的值。