class Solution(object):
def minimumDeleteSum(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: int
"""
# mxn
m = len(s1)
n = len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
dp[0][0] = 0
psum1 = 0
for i in range(1, n+1):
psum1 += ord(s2[i-1])
dp[0][i] = psum1
psum2 = 0
for j in range(1,m+1):
psum2 += ord(s1[j-1])
dp[j][0] = psum2
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:
p1 = dp[i-1][j]+ord(s1[i-1])
p2 = dp[i][j-1]+ord(s2[j-1])
dp[i][j] = min(p1,p2)
return dp[-1][-1]
712. 两个字符串的最小ASCII删除和
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 回文串的特点是，逆序输出和正序输出是一样的。所以这道题可以转化为：如果将此字符串逆序输出，那么两个字符串的最长公共...
- 给出一个字符串代表的正整数A和一个整数k(K<=n)，删除其中的k位数字，使得剩下的数字产生最小的正整数。例如：A...
- 我非常喜欢身处的这个时代。它所提供的可能性、人与人之间巨大的差异，太刺激了！ 如果我们原地不动的话，不去看、不去听...
- 现在过得就是是神仙的日子，如果有了钱，还能过这样的日子就太好了。 这句话是马哥说的。他说的时候，感觉他更在意的是现...
