给出两个字符串s1和s2，可以各自删除一些字符使得剩下的两个字符串相同，问删除的字符的ASCII码值之和最少为多少，DP
转移方程：
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]))
1 #712
2 #Runtime: 427 ms (Beats 68.49%)
3 #Memory: 17.2 MB (Beats 49.31%)
4
5 class Solution(object):
6 def minimumDeleteSum(self, s1, s2):
7 """
8 :type s1: str
9 :type s2: str
10 :rtype: int
11 """
12 n, m = len(s1), len(s2)
13 dp = [[0] * (m + 1) for _ in range(n + 1)]
14 for i in range(1, n + 1):
15 dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
16 for i in range(1, m + 1):
17 dp[0][i] = dp[0][i - 1] + ord(s2[i - 1])
18 for i in range(1, n + 1):
19 for j in range(1, m + 1):
20 if s1[i - 1] == s2[j - 1]:
21 dp[i][j] = dp[i - 1][j - 1]
22 else:
23 dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), dp[i][j - 1] + ord(s2[j - 1]))
24 return dp[n][m]