🐰😺🔮 兔猫信奥学院的镜像回文探秘 🔮😺🐰

在兔猫信奥学院的魔法图书馆里，流传着一面“镜影之镜”：它能够映出字符串的回文形态。小兔和小猫拿到了一段咒语文本 $s$，需要在魔镜前对其施展“字符插入术”，每次可以在任意位置加入一个字符，直到整个咒语变成回文。请问，你们最少需要施展多少次插入术，才能让咒语成为回文串？

输入格式

输入一行，包含字符串 s。

• $1 \le |s| \le 2000$
• $s$ 仅由小写英文字母组成。

输出格式

输出一个整数，表示将 s 变成回文串所需的最少插入次数。

示例 1

zzazz

0

• 解释：
  “zzazz” 已经是回文，无需任何插入。

示例 2

mbadm

2

• 解释：
  可通过插入字符变为 “mbdadbm” 或 “mdbabdm”，共需 2 次插入。

示例 3

leetcode

5

• 解释：
  最优可变为 “leetcodocteel”，需 5 次插入。

🎓 探秘提示：
通过将“最少插入”转化为“最长回文子序列”，你可以利用 LCS 动态规划巧妙求解。掌握此技巧后，还可进一步优化空间至 $O(n)$，并探索“最少删除”与“编辑距离”等更深层变形。祝探秘愉快！