线性动态规划：最小插入次数构造回文串（进阶版——允许删除操作） 题目描述 给定一个字符串 s ，你可以进行三种操作：插入一个字符、删除一个字符或替换一个字符（每次操作代价均为 1）。要求通过一系列操作将 s 转换为回文串，并返回 最小操作次数 。注意：替换操作允许将字符替换为任意字符。 解题思路 此问题可视为 编辑距离问题 的变种，目标是将字符串转换为回文串。定义动态规划状态 dp[i][j] 表示将子串 s[i:j] （闭区间）转换为回文串所需的最小操作次数。通过比较首尾字符，逐步向中间收缩，分类讨论操作策略。 详细步骤 状态定义 设 dp[i][j] 表示使子串 s[i...j] 成为回文的最小操作次数（ 0 ≤ i ≤ j < n ）。 边界条件 当 i == j ：单字符本身就是回文，操作次数为 0。 当 i > j ：空串视为回文，操作次数为 0。 状态转移方程 考虑子串 s[i...j] ： 情况1 ：若 s[i] == s[j] ，两端字符已匹配，无需操作两端，直接处理内部子串： dp[i][j] = dp[i+1][j-1] 。 情况2 ：若 s[i] != s[j] ，需通过操作使两端匹配，有三种选择： 插入 ：在 j 后插入 s[i] ，使 s[i] 与新增字符匹配，然后处理 s[i+1...j] ： dp[i][j] = dp[i+1][j] + 1 。 删除 ：删除 s[i] ，然后处理 s[i+1...j] ： dp[i][j] = dp[i+1][j] + 1 。 替换 ：将 s[j] 替换为 s[i] （或反之），使两端匹配，然后处理 s[i+1...j-1] ： dp[i][j] = dp[i+1][j-1] + 1 。 取三种操作的最小值： dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1 。 遍历顺序 由于 dp[i][j] 依赖 i+1 和 j-1 （即左下方、下方、左方的状态），需从子串长度由小到大遍历： 外层循环枚举子串长度 len 从 2 到 n 。 内层循环枚举起始下标 i 从 0 到 n-len ，计算 j = i+len-1 。 最终答案 返回 dp[0][n-1] ，即整个字符串的最小操作次数。 示例演示 以 s = "abca" 为例： 初始化：单字符子串操作次数为 0。 长度 2： "ab" ： s[0]!=s[1] ， dp[0][1] = min(dp[1][1], dp[0][0], dp[1][0])+1 = min(0,0,0)+1 = 1 。 "bc" ：同理得 dp[1][2] = 1 。 "ca" ： dp[2][3] = 1 。 长度 3： "abc" ： s[0]!=s[2] ， dp[0][2] = min(dp[1][2], dp[0][1], dp[1][1])+1 = min(1,1,0)+1 = 1 。 "bca" ： s[1]!=s[3] ， dp[1][3] = min(dp[2][3], dp[1][2], dp[2][2])+1 = min(1,1,0)+1 = 1 。 长度 4： "abca" ： s[0]==s[3] ， dp[0][3] = dp[1][2] = 1 。 最终结果为 1 ，例如将 'b' 替换为 'c' 得到 "acca" 。 复杂度分析 时间复杂度：O(n²)，需填充 n×(n+1)/2 个状态。 空间复杂度：O(n²)，可优化至 O(n)（仅保留当前行和上一行）。