区间动态规划例题：最小插入次数构造回文串问题 题目描述 给定一个字符串 s ，你可以在任意位置插入任意字符，求最少需要插入多少次才能将 s 变成回文串。例如： 输入 s = "ab" ，输出 1 （插入 'a' 得 "aba" 或插入 'b' 得 "bab" ）。 输入 s = "abcde" ，输出 2 （例如插入后得 "abcdcba" ）。 解题思路 定义 dp[i][j] 表示将子串 s[i:j] （左闭右闭区间）变为回文串所需的最小插入次数。目标是求 dp[0][n-1] 。 关键思路： 如果 s[i] == s[j] ，则两端字符已匹配，只需考虑内部子串 s[i+1:j-1] 的插入次数。 如果 s[i] != s[j] ，则需在左侧或右侧插入字符以匹配另一端，取两种操作的最小值再加 1。 状态转移方程 当 s[i] == s[j] ： dp[i][j] = dp[i+1][j-1] 当 s[i] != s[j] ： dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 边界条件： 当 i == j 时，子串长度为 1，已是回文，插入次数为 0。 当 i > j 时，视为空串，插入次数为 0。 逐步计算示例（s="abca"） 初始化 dp 表（4×4），对角线 dp[i][i]=0 ： 按区间长度 L=2 开始计算： [0,1]:"ab" ： s[0]!=s[1] → min(dp[1][1], dp[0][0])+1 = min(0,0)+1 = 1 [1,2]:"bc" ：同理得 1 [2,3]:"ca" ：同理得 1 长度 L=3 ： [0,2]:"abc" ： s[0]!=s[2] → min(dp[1][2], dp[0][1])+1 = min(1,1)+1 = 2 [1,3]:"bca" ： s[1]!=s[3] → min(dp[2][3], dp[1][2])+1 = min(1,1)+1 = 2 长度 L=4 ： [0,3]:"abca" ： s[0]==s[3] → dp[1][2] = 1 （内部 "bc" 需插入 1 次） 最终结果： dp[0][3] = 1 。 总结 通过填充上三角 dp 表，最终得到最小插入次数。时间复杂度 O(n²)，空间复杂度可优化至 O(n)。此问题本质是求字符串与其反转的最长公共子序列（LCS），答案为 n - LCS(s, s_reversed) 。