百年图书馆即将举办「丝绸之路古籍特展」，策展人需将空展架整理为特定古籍陈列序列。展架由 n 个格位组成，初始均为空槽（标记为 _）。每个格位需放置的文物用敦煌文书编号表示（如 H=汉简，T=吐蕃卷轴，U=回鹘文书，数字 1=特殊藏品编码）。

修复规则：
文物修复团队每次操作可将任意连续区间的空槽或已有文物整体替换为另一个文物（如将 [3-5] 替换为 T），另一个文物层会完全覆盖旧层。

注意：频繁替换会损伤文物，需计算最小替换次数以还原目标陈列序列，这对文物保护至关重要。

一个长度不超过 50 的字符串，包含大写字母（H/T/U）或字符 1，作为目标陈列序列。

输出一个整数，表示最少操作次数。

样例解释：

1. 覆盖全部为 T，此时展架状态为 TTTTT。

2. 覆盖第 1 位为 H，此时展架状态为 HTTTT。

3. 覆盖第 4 位为 U，此时展架状态为 HTTUT，达到目标陈列序列，最少的操作次数是 3 次。

说明：如果采用其他覆盖方法，如第一步全部覆盖为 H，第二步覆盖 2-3 位为 T，第三步覆盖第 4 位为 U，第四步覆盖第 5 位为 T，则需要 4 次操作，无法少于 3 次。

PTA 第八次认证 T4

区间DP