本文共 3267 字，大约阅读时间需要 10 分钟。
题目：
Given two strings
Example 1:s1,s2, find the lowest ASCII sum of deletedcharacters to make two strings equal.Input: s1 = "sea", s2 = "eat" Output: 231 Explanation:Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.Deleting "t" from "eat" adds 116 to the sum. At the end, both stringsare equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.Example 2:
Input: s1 = "delete", s2 = "leet" Output: 403Explanation: Deleting "dee" from "delete" to turn the string into"let", adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned bothstrings into "lee" or "eet", we would get answers of 433 or 417, which are higher.Note:
0 < s1.length, s2.length <= 1000. All elements of each string will have an ASCII value in[97, 122].
解释：
动态规划dp[i][j]表示s1的前i个字母和s2的前j个字母变成一样所需要的最小ASCII和，则一共有三种情况 1.dp[i-1][j]+s1[i],从dp[i-1][j]到dp[i][j]是多考虑了s1的一个字符，但是s2的字符数没有变，所以想要相同的话必须删除s1[i]，考虑ASCII的话就是加上s1[i]的ASCII 2.dp[i][j-1]+s2[j],删除s2[j] 3.dp[i-1][j-1]+a ,如果s1[i]==s2[j],则a=0,如果s1[i]!=s2[j],则a=s1[i]+s2[j] 4.在上述三种情况中找最小值 5.这种方法在python中超时了，反正速度特别慢，还是用下面的方法吧： 6.最长公共子序列解法：所有的减去2*相等的字符的ASCII的最大值(即最长公共子序列LCS)，等于题目所需的最小值 最长公共子序列只能求长度，如何求具体的元素？ 答：求lcs（subsequence）的时候不是+1而是+ord(s[i]) 最后返回的是dp[m][n]而不是maxLen。(lcsubarray和lcsubsequence的写法略有不同) python代码: class Solution(object): def minimumDeleteSum(self, s1, s2): """ :type s1: str :type s2: str :rtype: int """ def lcsubsequence(s1,s2): m=len(s1) n=len(s2) dp=[[0]*(n+1) for _ in xrange(m+1)] for i in xrange(1,m+1): for j in xrange(1,n+1): if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+ord(s1[i-1]) else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) return dp[m][n] m=len(s1) n=len(s2) if m==0 and n==0: return 0 if m==0: return sum(map(ord,s2)) if n==0: return sum(map(ord,s1)) return sum(map(ord,s1+s2))-2*lcsubsequence(s1,s2)
c++代码：
class Solution { public: int minimumDeleteSum(string s1, string s2) { int m=s1.size(),n=s2.size(); if (m==0 && n==0) return 0; if (m==0) return accumulate(s2.begin(),s2.end(),0); if (n==0) return accumulate(s1.begin(),s1.end(),0); return accumulate(s1.begin(),s1.end(),0)+accumulate(s2.begin(),s2.end(),0)-2*subsequence(s1,s2); }; int subsequence(string s1,string s2) { int m=s1.size(),n=s2.size(); vector >dp(m+1,vector (n+1,0)); for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+s1[i-1]; else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; }}; 总结：
这道题和 以及 一起学习，718是求lcsubarray，583是利用了lcsubsequence。 其实对于m和n是否为0的判断是不必要的，因为题目已经限定了字符串不为空，但是python中删掉判断居然变慢了很多，c++倒是不变，为什么？？？不过为了以后lcs的应用，还是把判断加上吧… 转载地址：http://nwmcn.baihongyu.com/