python中自上而下的動態編程

Question

我想用Python 3解決以下問題：https://www.hackerrank.com/contests/projecteuler/challenges/euler015。

以下是我的代碼：

def dp(x,y): 
    global MEMO,N,M 
    if x>N or y>M:return 0 
    if x==N and y==M: 
     return 1 
    if MEMO[x][y]!=-1:return MEMO[x][y] 
    MEMO[x][y]=(dp(x+1,y)+dp(x,y+1))%1000000007 
    return MEMO[x][y] 

MEMO=[[-1]] 
N=0 
M=0 
tc=int(input()) 
while tc: 
    tc-=1 
    N,M=map(int,input().split()) 
    MEMO=[[-1]*(M+1)]*(N+1) 
    print(dp(0,0)) 

然而，對於給定的測試用例，它給了答案3（不是6）。我認爲這與本地/全球範圍內的變量範圍有關。我哪裏錯了？

Answer 1

此：

MEMO=[[-1]*(M+1)]*(N+1) 

使得MEMO包含(N+1)引用相同的列表。這可能不是你想要的。

Answer 2

MEMO=[[-1]*(M+1)]*(N+1)複製列表[-1]M+1時間，但它與列表的相同實例這樣做。打印出來看發生了什麼事情：

>>> M=2 
>>> N=2 
>>> MEMO=[[-1]*(M+1)]*(N+1) 
>>> MEMO[0].append(1) 
>>> MEMO 
[[-1, -1, -1, 1], [-1, -1, -1, 1], [-1, -1, -1, 1]] 

查看如何他們都被append方法突變？那是因爲它們實際上是相同的列表。這個問題被稱爲aliasing。

您可以通過每次構建一個新的列表解決這個問題：

MEMO=[[-1 for x in xrange(M+1)] for x in xrange(N+1)]