leetcode 712 Minimum ASCII Delete Sum for Two Strings 详细解答
leetcode 712 Minimum ASCII Delete Sum for Two Strings 详细解答
解法1
这个题牵涉到两个数组的一些比较关系,会想到用动态规划求解。
至于怎么求解,这里说的是删到的字母ASCII码之和,这里换个思路可以求两个字符串所有字母的ASCII码之和减去两个字符串相同子序列出现的字母的ASCII码值之和。
所以状态转移方程就是求两个字符串相同序列的和。
F( i+1, j+1 ) 表示字符串 s1[0 … i] 和 s2[0 … j]相同子序列ASCII的和。
所以代码如下:
时间复杂度O(MN), 空间复杂度O(MN)
另一种解法空间复杂度是O(M),思路是一样的。留给大家自己参考: