Ausarbeitung des Binomialkoeffizienten in Python mit Memoization

Question

Ich versuche, mich selbst dynamische Programmierung beizubringen und übte eine Frage aus http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/. Ich habe zuerst die Frage in Java versucht und mein Code gibt die richtigen Ergebnisse. Java-Code:

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]; 
} 

aber als ich versuchte, die gleiche Sache in Python zu implementieren, konnte ich nicht und seltsame Ergebnisse bin immer, z.B. wenn n 5 ist und k 2 ist, bekomme ich 13, nicht 10. Ich bin ziemlich neu bei Python, also mag etwas offensichtliches fehlen, aber wenn jemand helfen könnte, würde das sehr geschätzt werden. Python-Code:

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

Alles in Ihrem Code ist außer der Initialisierung korrekt. Dies könnte geschehen, weil Sie möglicherweise nicht vollständig wissen, wie Listen funktionieren.

Schauen Sie sich diese Aussage und lässt verstehen, was es tut:

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

Operator * nur repliziert Kopien von was auch immer als Liste zur Verfügung gestellt. Also sind alle Listen im Wesentlichen gleich und beziehen sich auf eine Liste.

Um dies zu vermeiden, müssen Sie es einzeln initialisieren. Etwas wie folgt aus:.

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

So ist der modifizierte Code so etwas wie dieses werden würde (. Nur Änderung der Initialisierungsmethode hat)

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)) 

Als Beratung, in der Regel Listen werden für die Umsetzung memoization nicht verwendet In Python werden stattdessen andere Methoden verwendet, die Sie vielleicht selbst betrachten möchten.

Answer 2

Ich denke, es gibt keine Notwendigkeit dieser Bedingung if dp[n][k] > 0:.

Versuchen Sie es:

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