1. 题目

传送门= ̄ω ̄=

2. 题解

。。。最基础的动规题调了我一个小时。。。
。。。以后再也不在11点以后写题了。。。

设$f(i,j)$为序列1前$i$个字符和序列2前$j$个字符产生的最大相似度。
第$i$个字符和第$j$个字符不一定要对齐。

设$s(i,j)$表示字符$i$和字符$j$产生的相似度。
序列分别为str1,str2。
$f(i,j)=max(f(i-1,j)+s(str1[i],-)),f(i,j-1)+s(str2[j],-),f(i-1,j-1)+s(str1[i],str2[j]))$

代码: