蓝桥杯-最优包含

?最优包含?
?题目描述
题目链接

?输入

ABCDEABCD
XAABZ

?输出

3

☀️思路

线性dp题，与 最短编辑距离 相似
 使用闫氏dp法进行分析

把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配,那么修改这一位之前                                             a的前i-1个字符应该和b的j-1个字符相匹配(相同)，f[i-1][j-1]+1 如果本来a[i]与b[j]就相等，那就不用改   f[i-1][j-1]+0
之后对图中转移方程取min即可解出

 初始化：
因为求的是最小值，所以先对所有f赋为正无穷f[i][0]代表a的前i个字符包含b的前0个字符的操作数,b的前0个字符即空串，因为空串是任意串的子串，不需要进行更改操作，所以操作数为0f[0][j]代表a的前0个字符包含b的前j个字符的操作数，因为a的前0个字符即空串，空串无论怎么修改任然是空串，因此应该赋值为正无穷，但此前我们已

蓝桥杯-最优包含最先出现在Python成神之路。