首页 > 代码库 > 动态规划 — 计算二项式系数

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

如果问题是由交叠的子问题所构成的,那么我们就可以用动态规划技术来解决它。也就是说,一个问题的解可由它的规模更小的子问题的解递推得出。由于子问题的交叠性质,所以采用递归地方法一次又一次地求解子问题时,进行了很多重复的工作。所以动态规划法建议:把子问题的解存入某个表中,通过表一步步反解出原始问题。斐波那契数列就是一个很好的例子:
F(n) = F(n-1) + F(n-2)     当n≥2
F(0) = 0
F(1) = 1
如果直接采用递推公式求解第n个斐波那契数,那么会重复大量的无用工作,效率变得极为低下。同时注意到,F(n-1)和F(n-2)是两个规模更小的具有交叠性质的子问题,所以可以使用动态规划法求解F(n)。方法是创建一个表保存每一个斐波那契数。这使得每个斐波那契数只求解了一次,求解F(n)只需要查表获得F(n-1)和F(n-2)的值即可。

动态规划其实和一般的递归方法很相似,核心在于求出一个递推式和一个边界条件。不同的是,动态规划会保存中间结果并利用这些中间结果解出最终的问题。

下面一个例子是利用动态规划计算二项式系数。

给出n和k,求出二项式系数C(n,k)。在这里,我们只关心两个信息就够了:
  • C(n,k) = C(n-1,k-1) + C(n-1,k)    当n>k>0
  • C(n,0) = C(n,n) = 1
从上面的递推式可以看到两个较小的具有交叠性质的子问题C(n-1,k-1)和C(n-1,k),所以,计算二项式系数是把动态规划应用于非最优化问题的一个标准例子。

废话不多说,直接上代码:
#include <iomanip>
#include <iostream>
 
using namespace std;
 
int main()
{
    int n, k;
 
    cout << "求C(n,k),请输入n和k(k <= n):";
    cin >> n >> k;
     
    int **p;
    p = new int*[n + 1];
    for (int i = 0; i <= n; i++)
        p[i] = new int[k + 1];
     
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= k; j++)
            p[i][j] = 0;
     
    for (int i = 0; i <= n; i++)
        p[i][0] = 1;  // C(n,0) = 0
 
    for (int i = 0; i <= k; i++)
        p[i][i] = 1;  // C(n,n) = 1
 
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < (i > k ? k + 1 : i); j++)
            p[i][j] = p[i - 1][j - 1] + p[i - 1][j];
 
    //cout.flags(ios::right);   // 输出对齐
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
            cout << setw(5) << p[i][j] << ' ';
 
        cout << endl;
    }
     
    // 销毁空间
    for (int i = 0; i <= n; i++)
        delete[] p[i];
 
    delete[] p;
 
    return 0;
}

运行结果:


矩阵右下角便是所要求的结果。可以看到,这个矩阵正是杨辉三角,即帕斯卡三角的一部分。

算法效率:
该算法的核心操作是加法,时间复杂度为Θ(nk)。

参考:
《算法设计与分析基础》8.1节。