算法一：使用组合恒等式优化

例如，由于 $C^{k}_{n} = C^{n - k}_{n}$，可以只计算较小的一边，以减少计算量。

这里提供一个基于动态规划和组合恒等式的高效 C++ 实现示例：

// 动态规划计算组合数 C(n, k)
int binomialCoeff(int n, int k){
    vector<vector<int>> C(n + 1, vector<int>(k + 1, 0));

    for(int i = 0; i <= n; i ++ ){
        for(int j = 0; j <= min(i, k); j ++ )
            if(j == 0 || j == i) C[i][j] = 1;  // Base cases
            else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    return C[n][k];
}

【注】：$C(n,k)$ 表示 $C^{k}_{n}$。

当数据范围 $n$ 和 $k$ 最大为$1000$时，可以考虑使用基于前缀和的动态规划方法来计算组合数 $C(n,k)$。这种方法可以有效地处理相对较大的数据范围，而且能够在较短的时间内完成计算。

算法二：使用一维滚动数组优化空间

动态规划的一个重要技巧是使用滚动数组来减少空间复杂度。对于组合数计算，我们只需要保留当前行和上一行的数据。由于每个 $C(i,j)$ 只依赖于 $C(i−1,j−1)$ 和 $C(i−1,j)$，我们可以用一维数组从后向前更新，这样可以在不覆盖还未使用的数据的情况下完成更新。

以下是使用滚动数组实现组合数计算的 C++ 代码示例：

// 使用滚动数组计算组合数 C(n, k)
int binomialCoeff(int n, int k){
    vector<int> C(k + 1, 0);
    C[0] = 1;  // C(n, 0) is 1 for any n

    for(int i = 1; i <= n; i ++ ){
        for(int j = min(i, k); j > 0; j -- ) C[j] = C[j] + C[j - 1];
    }

    return C[k];
}

计算单个组合数模上质数 $p$ 的最高效算法：

typedef long long LL;

LL CmodP(LL n, LL k, LL p){
    LL res = 1, inv = 1;
    for(LL i = 1; i <= k; ++ i){
        res = res * (n - i + 1) % p;
        inv = inv * i % p;
    }
    for(LL exp = p - 2; exp; exp >>= 1, inv = inv * inv % p){
        if(exp & 1) res = res * inv % p;
    }
    return res;
}

这段代码实现了组合数 $C^{k}_{n}\mod p$ 的计算，其中 $p$ 是一个素数。它使用了模逆元和快速幂算法（费马小定理）来高效地计算模 $p$ 下的组合数。总体的时间复杂度为 $O (k + \log p)$。

算法三：直接计算

typedef long long LL;

LL C(LL n, LL k) {
    if(k > n) return 0;
    if(k > n - k) k = n - k;
    LL res = 1;
    for(LL i = 1; i <= k; ++ i){
        res = res * (n - i + 1) / i;
    }
    return res;
}

总结

算法一（动态规划） 使用了经典的动态规划方法来计算组合数，空间复杂度为 $O(nk)$，时间复杂度也为 $O(nk)$。这种方法非常适合当你需要重复计算多个组合数时，因为它保存了中间结果，但对于单次计算来说，它可能不是最高效的。

算法二（滚动数组优化的动态规划） 通过使用滚动数组来降低空间复杂度到 $O(k)$，同时保持 $O(nk)$ 的时间复杂度。这种方法比上一种方法在空间使用上更高效，对于单个组合数的计算来说，它是一个更好的选择。

算法三（直接计算方法） 直接计算组合数，时间复杂度为 $O(k)$，空间复杂度为 $O(1)$。这是对于计算单个组合数而言最直接且高效的方法，尤其是当 $k$ 相对于 $n$ 很小的时候。