首页 > 专题系列 > 算法分析 > 动态规划(9)-二项式系数
2014
03-16

动态规划(9)-二项式系数

以下是常见的二项式系数的定义:

1) 一个二项式系数 C(n, k)  可以被定义为(1 + X)^n 的展开式中  X^k  的系数。

2) 二项式系数对组合数学很重要,因它的意义是从n件物件中,不分先后地选取k件的方法总数,因此也叫做组合数.

问题

写一个函数,它接受两个参数n和k,返回二项式系数C(n,k)。例如,你的函数应该返回6 当n = 4 k = 2时,返回10当 n = 5 k = 2时。

1) 最优子结构

C(n,k)的值可以递归地使用以下标准公式计算,这个应该是高二的数学:

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

2) 重叠子问题

下面是一个直接用上面的公式写的递归程序解决:

// 直接递归实现
#include<stdio.h>

// 返回二项式系数的值 C(n, k)
int binomialCoeff(int n, int k)
{
  // 基本情况
  if (k==0 || k==n)
    return 1;

  // Recur
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

/* 测试程序 */
int main()
{
    int n = 5, k = 2;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

应该指出的是,上面的程序一次又一次计算相同的子问题。看到下面的递归树n = 5 k = 2。函数C(3,1)执行两次。对于较大的n 值,将会有许多共同的子问题。

                             C(5, 2)
                    /                      \
           C(4, 1)                           C(4, 2)
            /   \                          /           \
       C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)
                /    \               /     \               /     \
         C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)
                   /        \              /   \            /    \
               C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)

很明显,这个问题可以用动态规划来解决,因为包含了动态规划的两个基本属性(见重叠子问题最优子结构

和经典的动态规划解决办法一样,这里通过自下而上的构建数组 C[][] 保存子问题的值。

#include<stdio.h>
int min(int a, int b);
// 返回二项式系数 C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n+1][k+1];
    int i, j;

    // 通过自下而上的方式打表
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            if (j == 0 || j == i)
                C[i][j] = 1;
             else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    return C[n][k];
}
int min(int a, int b)
{
    return (a<b)? a: b;
}

/* 测试程序*/
int main()
{
    int n = 5, k = 2;
    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
    return 0;
}

时间复杂度: O(n*k)

空间复杂度: O(n*k)

其实,空间复杂度可以优化到 O(k).  但是实际应用中,还是直接用二维数组打表使用比较多。

// 空间优化
int binomialCoeff(int n, int k)
{
    int* C = (int*)calloc(k+1, sizeof(int));
    int i, j, res;

    C[0] = 1;

    for(i = 1; i <= n; i++)
    {
        for(j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j-1];
    }
    res = C[k];  // 在释放内存前存储结果
    free(C); 
    return res;
}

参考:http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/


  1. [email protected]