动态规划:计算二项式系数

2016年01月06日 原创
关键词: C++ 数据结构 算法 动态规划
摘要 计算二项式系数是把动态规划应用于非最优化问题的一个标准例子。

回忆一下我们在初等排列组合中学过的知识--二项式系数,基座C(n,k),它是来自于一个n元素集合的k元素组合(子集)的数量(0≤k≤n)。“二项式系数”这个名字来源于这些数字出现在二项式公式之中。

(a+b)n=C(n,0)an+....+C(n,k)an-kbk+...+C(n,n)bn

在二项式系数的多种特性之中,我们只关心两种:

当n>k>0时,C(n,k)=C(n-1,k-1)+C(n-1,k)

以及

C(n,0)=C(n,n)=1

通过以上两个公式,我们可以对C(n,k)进行计算。

下面的伪代码实现了这个算法。

算法  Binomial(n,k)

   //用动态规划算法计算C(n,k)

   //输入:一对非负整数n≥k≥0

   //输出:C(n,k)的值

   for i←0 to n do

     for j←0 to min(i,k) do

       if j=0 or j=i

         C[i,j]←1

       else C[i,j]←C[i-1,j-1]+C[i-1,j]

   return C[n,k]

其中min(i,k)是因为计算C(n,k)的时候,不需要计算任意一行k列之后的数据,提高了效率。

该算法的效率属于Θ(nk)。

下面是该算法的c++代码,其中只使用了一段额外的线性存储空间,进行了复用,而不是申请了二维数组。

#include<iostream>
#include<algorithm>
#define maxn 1000
using namespace std;
int data[maxn];
int binomial(int n, int k) {
    int temp = 0;
    int ttemp = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i,k); j++) {
            if (j == 0 || j == i) {
                data[j] = 1;
                temp = 1;
            }
            else {
                ttemp = data[j];
                data[j] = temp + data[j];
                temp = ttemp;
            }
        }
    }
    return data[k];
}
int main() {
    cout << binomial(100, 3) << endl;
    return 0;
}

运行结果: