메모를 사용하여 파이썬에서 이항 계수 계산하기

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 일 때 나는 10이 아니라 13을 얻습니다. 저는 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)) 

조언으로, 일반적으로 목록은 메모이 제이션을 구현하는 데 사용되지 않습니다 대신에 파이썬에서는 다른 방법을 사용하여 직접 볼 수도 있습니다.

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