题解：P12211 [蓝桥杯 2023 国 Python B] 翻转

· · 题解

思路

简单的 dp。

定义 f(i,0) 表示对于第 i 个字符串按正常顺序的最短长度， f(i,1) 表示对于第 i 个字符串按翻转后顺序的最短长度。

那么分别判断在正常和翻转情况下与前一个字符串正常和翻转情况下前后能否相连即可。

时间复杂度为 O(n)。