问题
给定两个字符串，删除字符使得两个字符串相等，如何删使得删除的字符的ASCII和最小。
Input: s1 = "sea", s2 = "eat"
Output: 231 Explanation: 115(s) + 116(t) = 231
思路
用dp[i][j]表示s1[:i]和s2[:j]之间的解。
如果s1[i-1] == s2[j-1]，dp[i][j] = dp[i-1][j-1]。两字符相等，不需要删除，等于之前的值。 否则，dp[i][j] = min(dp[i-1][j]+ s1[i-1], dp[i][j-1] + s2[j-1])。不等，需要删除，在之前的结果基础上，计算删s1字符的代价和删s2字符的代价哪个小。时间复杂度O(n*m)，空间复杂度O(n*m)
代码
class Solution(object): def minimumDeleteSum(self, s1, s2): """ :type s1: str :type s2: str :rtype: int """ dp = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)] for i in range(1,len(s2)+1): dp[0][i] = dp[0][i-1] + ord(s2[i-1]) for j in range(1,len(s1)+1): dp[j][0] = dp[j-1][0] + ord(s1[j-1]) for i in range(1,len(s1)+1): for j in range(1,len(s2)+1): if(s1[i-1]==s2[j-1]): dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j]+ord(s1[i-1]), dp[i][j-1]+ord(s2[j-1])) return dp[len(s1)][len(s2)]
相关知识
ord('a') == 97 #获取字符对应的ASCII码chr(97) == 'a' #获取ASCII码对应的字符chr(0x61) == 'a' #可以输入十六进制hex(97) == '0x61' #获取整数对应的十六进制字符串oct(97) == '0141' #获取整数对应的八进制字符串