使用数组来改善递归二项分布算法的执行时间？

Question

作为一名初学程序员,我最近买了Robert Sedgewick/Kevin Wayne的书"算法 - 第四版",我非常感谢每一章末尾的练习.然而,有一个练习(看起来很简单)让我疯狂,因为我无法找到解决方案.

你必须采用这种递归算法,找出在n次试验中获得准确k次成功的概率,其中p是一个事件成功的可能性.给出的算法基于递归二项分布论坛.

public static double binomial(int n, int k, double p) {
    if (n == 0 && k == 0)
        return 1.0;
    else if (n < 0 || k < 0)
        return 0.0;
    return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
}

本练习的目的是通过在数组中保存计算值来加快此算法的速度.通过使用另一种获得二项分布[p(x)= nCr*p ^ k*(1 - p)^(n - k)]的方法,我已经使这个算法变得更快了,它使用迭代方法来寻找阶乘.但是,我不明白如何使用数组来改善此上下文中的执行时间.

任何帮助将不胜感激!

......在有人问之前,这不是作业!

Answer 1

本书试图教你一种叫做memoization的特殊编程技术,这是一种被称为动态编程的更广泛的技术.当然,在现实生活中,了解封闭形式的解决方案要好得多,但不能解决这个问题.

无论如何,这个想法是通过一个二维数组作为你的第四个参数,以填补它NaN最初S,并检查是否有针对给定的组合解决方案n和k计算任何东西之前在数组中.如果有,请归还; 如果没有,则递归计算,存储在数组中,然后返回它.