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

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

2024-07-07 17:42:54   227人阅读

如果问题是由交叠的子问题所构成的，那么我们就可以用动态规划技术来解决它。也就是说，一个问题的解可由它的规模更小的子问题的解递推得出。由于子问题的交叠性质，所以采用递归地方法一次又一次地求解子问题时，进行了很多重复的工作。所以动态规划法建议：把子问题的解存入某个表中，通过表一步步反解出原始问题。斐波那契数列就是一个很好的例子：
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节。


联系
我们