讨论一道算法题：编辑距离的进阶版
Hello，大家好：
今天遇见了一道特别变态的编辑距离的进阶版，求两个字符串的最大分数。
字符串的分数这么计算：只能增，不能删，不能替换，并且增加的字符只能是一个特殊字符，我们定义为 *
字符串只由A,B或C构成，以下面为例。
字符串A：CCCCC，字符串B：CCC
首先把字符串变成等长的，我们可以在CCC末尾增加**变成CCC**，然后，逐个字符比较，如果相等，分数+1，如果不相等，分数-4，如果比较的2个字符中有1个字符是*（且是连续的第一个*），分数-3，如果不是连续的第一个*，则-1
CCCCC和CCC**，第一个C和C，+1分，第二个C和C，+1分，第三个C和C，+1分，第4个C和*，-3分，第5个C和*，-1分（由于这个*不是连续的第一个*，因此只减1分）
例子2：字符串A：CDCF，字符串B：CECFFF。首先在字符串A最后面补两个*，变成CDCF**，然后开始比较。第一个C和C，+1分，第二个D和E，-4分，第三个C和C，+1分，第四个F和F，+1分，第5个*和F，-3分，第6个*和F，-1分
*可以加在字符串的任何位置，且两个字符串都可以加，求所有方案中分数最大的，输出最大分数
大家有啥想法。。。。。和编辑距离有相似之处。。但是感觉比编辑距离更难。。。。
#算法题#
投递腾讯音乐娱乐集团等公司7个岗位 >
查看29道真题和解析
