寫Leetcode的時候突然出現(xiàn)的一個錯誤，想要記錄一下，也不知道起個什么標題好，所有隨便起了一個大概相關(guān)的標題

以Leetcode的題目開始引入

Leetcode的第72題

image.png

下面是解法（Python）

# 動態(tài)規(guī)劃
# 具體看leetcode講解
# 注意里面dp定義的細節(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定義，第一種定義是錯的，因為列表內(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)]是不一樣的，兩種答案不同，后者才是我們想要的答案，那么為什么會出現(xiàn)這種不同呢？

通過一個簡單的例子來看看

image.png

我們發(fā)現(xiàn)不同元素的id是一樣的，即它們都指向同一個內(nèi)存地址。

image.png

結(jié)論

dp = [[0] * (m+1)] * (n+1)和dp = [ [0] * (m + 1) for _ in range(n + 1)]打印出來一樣，但前者是列表里面n+1個元素都是指向同一個內(nèi)存地址，后者是不同的內(nèi)存地址。所以，建議定義二維列表的時候用列表生成式。