寫Leetcode的時(shí)候突然出現(xiàn)的一個(gè)錯(cuò)誤,想要記錄一下酗宋,也不知道起個(gè)什么標(biāo)題好,所有隨便起了一個(gè)大概相關(guān)的標(biāo)題
以Leetcode的題目開始引入
Leetcode的第72題
image.png
下面是解法(Python)
# 動(dòng)態(tài)規(guī)劃
# 具體看leetcode講解
# 注意里面dp定義的細(xì)節(jié)
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word1)
m = len(word2)
if n*m == 0:
return n+m
# 下面兩種dp定義斥扛,第一種定義是錯(cuò)的丹锹,因?yàn)榱斜韮?nèi)的元素id都相同
# dp = [[0] * (m+1)] * (n+1)
dp = [ [0] * (m + 1) for _ in range(n + 1)]
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
left = dp[i][j-1] + 1
down = dp[i-1][j] + 1
left_down = dp[i-1][j-1]
if word1[i-1] != word2[j-1]:
left_down += 1
dp[i][j] = min(left, down, left_down)
return dp[-1][-1]
代碼中列表定義的區(qū)別
看代碼注意到dp = [[0] * (m+1)] * (n+1)
和dp = [ [0] * (m + 1) for _ in range(n + 1)]
是不一樣的芬失,兩種答案不同,后者才是我們想要的答案棱烂,那么為什么會(huì)出現(xiàn)這種不同呢?
通過一個(gè)簡單的例子來看看
image.png
我們發(fā)現(xiàn)不同元素的id是一樣的哩治,即它們都指向同一個(gè)內(nèi)存地址。
image.png
結(jié)論
dp = [[0] * (m+1)] * (n+1)
和dp = [ [0] * (m + 1) for _ in range(n + 1)]
打印出來一樣业筏,但前者是列表里面n+1個(gè)元素都是指向同一個(gè)內(nèi)存地址鸟赫,后者是不同的內(nèi)存地址。所以抛蚤,建議定義二維列表的時(shí)候用列表生成式。