算法61---兩個字符串的最小ASCII刪除和【動態規劃】

一、題目：

給定兩個字符串s1, s2，找到使兩個字符串相等所需刪除字符的ASCII值的最小和。

示例 1:

輸入: s1 = "sea", s2 = "eat"
輸出: 231
解釋: 在 "sea" 中刪除 "s" 并將 "s" 的值(115)加入總和。
在 "eat" 中刪除 "t" 并將 116 加入總和。
結束時，兩個字符串相等，115 + 116 = 231 就是符合條件的最小和。

示例?2:

輸入: s1 = "delete", s2 = "leet"
輸出: 403
解釋: 在 "delete" 中刪除 "dee" 字符串變成 "let"，
將 100[d]+101[e]+101[e] 加入總和。在 "leet" 中刪除 "e" 將 101[e] 加入總和。
結束時，兩個字符串都等于 "let"，結果即為 100+101+101+101 = 403 。
如果改為將兩個字符串轉換為 "lee" 或 "eet"，我們會得到 433 或 417 的結果，比答案更大。

注意:

• 0 < s1.length, s2.length <= 1000。
• 所有字符串中的字符ASCII值在[97, 122]之間。

思路：動態規劃：時間O（M*N)，空間O（M*N)

dp[i][j]表示s1字符串第i個到s2字符串di第j個相等所需的代價。

子問題：dp[i][j-1]、dp[i-1][j]、dp[i-1][j-1]

狀態方程：如果s1[i] == s2[j]:dp[i][j] = dp[i-1][j-1]

否則：dp]i][j] =??dp[i][j] = min(dp[i][j-1] +ord(s2[j-1]),dp[i-1][j] + ord(s1[i-1]),dp[i-1][j-1] + ord(s1[i-1])+ord(s2[j-1]))

代碼：

    def minimumDeleteSum(self, s1, s2):""":type s1: str:type s2: str:rtype: int"""if not s1 and not s2:return  0if not s1 and s2:return sum([ord(ss) for ss in s2])if not s2 and s1:return sum([ord(ss) for ss in s1])m , n = len(s1) , len(s2)dp = [[0] * (n+1) for i in range(m+1)]dp[0][0] = 0for i in range(1,m+1):dp[i][0] = dp[i-1][0] + ord(s1[i-1])for j in range(1,n+1):dp[0][j] = dp[0][j-1] + ord(s2[j-1])for i in range(1,m+1):for j in range(1,n+1):if s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i][j-1] +ord(s2[j-1]),dp[i-1][j] + ord(s1[i-1]),dp[i-1][j-1] + ord(s1[i-1])+ord(s2[j-1]))return dp[-1][-1]

?