动态规划、字符串、区间动态规划、回文
动态规划，令给定的字符串为 $s$，设计 $dp_{l,r}$ 为使子串 $[l,r]$ 成为回文串需要插入的最小字符数量，初始化 $dp_{i,i}=0$。状态转移方程 $dp_{l,r}=\min(dp_{l+1,r-1}+[s_l \neq s_r],\min(dp_{l+1,r},dp_{l,r-1})+1)$，枚举区间长度计算，时间复杂度 $O(n^2)$。
最后修改：2024 年 05 月 26 日
© 允许规范转载