使用記憶法計算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

一切都是正確的，除了初始化。這可能是因爲你可能不完全知道列表是如何工作的。

看這個說法，讓瞭解它做什麼：

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中，而不是其他的方法，你可能想看看你自己的。

Answer 2

我覺得沒有必要這樣的條件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] 

鏈接：在你的代碼Working code