LeetCode 712. Minimum ASCII Delete Sum for Two Strings

712. Minimum ASCII Delete Sum for Two Strings

又是dp题目

题目:删掉两个字符串中的字符让两个字符串相同,并统计删掉的字符的ascii码总和,要求总和最低。

思路:也是动态规划,和最长公共子序列很像,是个变种。
有两种思路,第一种:继续按照最长公共子序列来做,算出了最长公共子序列之后,拿两个字符串的ascii码总和减去公共子序列的ascii码值,就是去掉的字符串的ascii码的和;第二种:反向算最长公共子序列,当dp计算的时候,如果字符不相等,进行ascii码的计算,相等则继续循环。

我采用的是第二种思路,用的递归写法,个人认为递归的写法比较简单,一下就能开写,不太需要思考。

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注