c++ - 使用动态规划计算二项式系数

Question

我写这段代码来求二项式系数_nC_k:

# include <bits/stdc++.h>
using namespace std;
int c[20][20];
void initialize()
{
    for(int i=0;i<20;i++) 
        for(int j=i;j<20;j++)
            c[i][j]=-1;
}
int binomCoeff(int n,int k)
{
    if(k==0||k==n) return 1;
    if(c[n][k]!=-1)
        return c[n][k];
    return c[n][k] =  binomCoeff(n-1,k-1) + binomCoeff(n-1,k);
}

int main()
{
    initialize();
    cout<<binomCoeff(4,2)<<endl;
}

我是动态规划的新手，所以找不到错误。

Answer 1

您正在为 k(小于或等于 n)使用第二个索引，但仅初始化更大的索引

for(int j=  0  ;j<20;j++)
or
for(int j=  0  ;   j <= i  ;j++)

请注意，此错误将在逐步调试过程中被发现。你为什么忽略这种方法？

附言这里使用的方法是 memoization - “自上而下”的动态规划。您还可以将“自下而上”动态规划实现为练习 - 按顺序填充表格并获得最后一个单元格结果。