使用 memoization 计算 python 中的二项式系数

Question

我正在尝试自学动态编程并正在练习 http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/ 中的一个问题。我首先尝试 Java 中的问题，我的代码给出了正确的结果。 Java代码：

 static int calculate(int n, int k){
    if(k == 0 || k == n)
        return 1;
    if(dp[n][k] != Integer.MAX_VALUE)
        return dp[n][k];
    else
        dp[n][k] = calculate(n - 1, k -1) + calculate(n-1, k );
    return dp[n][k];
}

然而，当我试图在 Python 中实现同样的事情时，我无法做到并且得到了奇怪的结果，例如当 n 为 5 且 k 为 2 时，我得到 13，而不是 10。我对 Python 很陌生，所以可能会遗漏一些明显的东西，但如果有人能提供帮助，我将不胜感激。 Python代码：

dp = [[-1] * 3] * 6

def calculate(n, k):
    if n == k or k == 0:
        return 1
    if dp[n][k] > 0:
        return dp[n][k]
    else:
        dp[n][k] = calculate(n-1, k-1) + calculate(n-1, k)
    return dp[n][k]

Answer 1

我觉得不需要这个条件if dp[n][k] > 0:.

试一试：

dp = [[-1] * 3] * 6

def calculate(n, k):
if n == k or k == 0:
    return 1
dp[n][k] = calculate(n-1, k-1) + calculate(n-1, k)
return dp[n][k]

Link : Working code

Answer 2

除了初始化之外，您的代码中的所有内容都是正确的。这可能是因为您可能不完全了解列表的工作原理。

看看这条语句，让我们理解它的作用：

dp = [[-1] * 3] * 6

运算符* 只是复制作为列表提供的任何内容的副本。所以所有列表本质上都是相同的并且引用一个列表。

为避免这种情况，您必须单独对其进行初始化。像这样：

dp = [[-1 for j in range(100)] for i in range(100)]

所以修改后的代码会变成这样（只是初始化方法有变化）

dp = [[-1 for j in range(100)] for i in range(100)]

def calculate(n, k):
    if n == k or k == 0:
        return 1
    if dp[n][k] > 0:
        return dp[n][k]
    else:
        dp[n][k] = calculate(n-1, k-1) + calculate(n-1, k)
    return dp[n][k]

print(calculate(5,2))

作为建议，在 python 中通常不使用列表来实现记忆，而是使用其他方法，您可能希望自己查看。

使用 memoization 计算 python 中的二项式系数

Working out the binomial coefficient in python using memoization

memoization

dynamic-programming

python-3.x