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

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 ，一种更广泛的技术，称为 dynamic programming .当然，在现实生活中知道一个封闭形式的解决方案要好得多，但在解决这个练习的上下文中就不是这样了。

无论如何，我们的想法是传递一个二维数组作为您的第四个参数，最初用 NaN 填充它，然后检查是否有给定 n 组合的解决方案> 和 k 在计算任何东西之前在数组中。如果有，请退回；如果没有，则递归计算，存储在数组中，然后才返回。