蓝桥杯 2019 最优包含 线性DP

[蓝桥杯 2019 国 B] 最优包含

题目描述

若字符串 S 中存在若干字符，能够按照原始顺序组合成与 T 完全一致的字符串，则称 S 包含 T。所谓包含关系，即 T 是 S 的子序列。现在给定两个字符串 S 与 T，要求确定需要对 S 中的多少个字符进行调整，才能使得调整后的字符串满足包含 T 的条件。

输入格式

提供两行输入，每行对应一个字符串。其中第一行所表示的字符串标记为 S，第二行对应的字符串标记为 T。这两个字符串均不为空，并且仅由大写字母组成。

输出格式

输出一个数值，用以表示最终结果。

样例分析与呈现

样例输入 #1

    ABCDEABCD
    XAABZ
    
    
      
      
    

样例输出结构解析

    3
    
    
      
    

提示

针对 20 \% 的测试案例，其参数范围设定为 1 \leq|T| \leq|S| \leq 20；

在 40 \% 的测试案例中，参数范围扩展至 1 \leq|T| \leq|S| \leq 100；

而对于全部测试案例，参数的上限则调整为 $1 \leq|T| \l