算法之二项分布(c/c++版)

二项分布是数学的概念，定义及公式定理不在此说明.
注：递归版第三步及递推都依赖于C（M-1，N-1）+C（M-1，N）=C（M，N）的变形
递归版:
（我给递归版注释了1 2 3 是为了解析非递归版(递推版)中同等的操作
1 2 3）方便我们理解是怎么让递归变成递推的

double binomial(int N, int k, double p)
{
    // 1
    if (N < 0 || k < 0)
        return 0.0;
    // 2
    if (N == 0 && k == 0)
        return 1.0;
    // 3
    return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
}

递归版貌似很好理解，运行binomail(10,5,0.25)能通过,当我们用binomail(100,25,0.25),电脑似乎就不给力了，几天几夜恐怕也不会有结果,这时间复杂都有点捉急啊,那下面我们就用点小空间改成递推吧

非递归版(递推版)：

double binomial(int N, int k, double p)
{
    if (N < 0 || k < 0) return 0.0;
    double **ret = new double*[N + 1];
    for (int i = 0; i < N + 1; ++i)
        ret[i] = new double[k + 1];
    //1完成递归版的2
    ret[0][0] = 1.0;
    //2完成递归版的1
    for (int i = 1; i < N + 1; ++i)
        ret[i][0] = (1.0 - p) * ret[i - 1][0];
    for (int j = 1; j < k + 1; ++j)
        ret[0][j] = 0.0;
    //3完成递归版的3
    for (int i = 1; i < N + 1; ++i)
        for (int j = 1; j < k + 1; ++j)
            ret[i][j] = (1.0 - p) * ret[i - 1][j] + p * ret[i - 1][j - 1];
    return ret[N][k];
}

尝试binomial(100,50,0.25)：