最小代价构造回文串问题（字符插入与删除） 题目描述： 给定一个字符串s，你可以进行两种操作：在任意位置插入一个字符，或者删除任意位置的字符。每次插入或删除的代价可能不同（本题中我们假设插入和删除的代价都为1）。你的目标是通过最少的操作次数，将字符串s转换为回文串。 解题过程： 问题分析： 回文串的特点是正读反读相同 我们需要找到最少的插入/删除操作来使字符串变成回文 关键观察：对于字符串两端的字符，如果它们相同，我们不需要任何操作；如果不同，我们有两种选择：删除左端字符或在右端插入相同字符，或者删除右端字符或在左端插入相同字符 定义状态： 设dp[ i][ j]表示将子串s[ i...j ]转换为回文串所需的最小操作次数 i和j分别表示子串的起始和结束索引（0 ≤ i ≤ j < n） 状态转移方程： 基本情况：当i = j时，单个字符本身就是回文，dp[ i][ j ] = 0 当i + 1 = j时，只有两个字符： 如果s[ i] = s[ j]，则dp[ i][ j ] = 0 如果s[ i] ≠ s[ j]，则dp[ i][ j ] = 1（删除一个或在另一端插入相同字符） 一般情况（j - i ≥ 2）： 如果s[ i] = s[ j]，则两端字符相同，不需要操作两端：dp[ i][ j] = dp[ i+1][ j-1 ] 如果s[ i] ≠ s[ j ]，则有两种选择： 操作左端字符：删除s[ i]或在右端插入s[ i]，代价为1 + dp[ i+1][ j ] 操作右端字符：删除s[ j]或在左端插入s[ j]，代价为1 + dp[ i][ j-1 ] 取最小值：dp[ i][ j] = min(1 + dp[ i+1][ j], 1 + dp[ i][ j-1 ]) 计算顺序： 按子串长度从小到大计算 先计算所有长度为1的子串，然后长度为2，依此类推，直到整个字符串 示例演示（字符串s = "abac"）： 长度1：dp[ 0][ 0]=0, dp[ 1][ 1]=0, dp[ 2][ 2]=0, dp[ 3][ 3 ]=0 长度2： dp[ 0][ 1]：'a'≠'b' → min(1+dp[ 1][ 1], 1+dp[ 0][ 0 ]) = min(1,1) = 1 dp[ 1][ 2]：'b'≠'a' → min(1+dp[ 2][ 2], 1+dp[ 1][ 1 ]) = min(1,1) = 1 dp[ 2][ 3]：'a'='c'? 不，'a'≠'c' → min(1+dp[ 3][ 3], 1+dp[ 2][ 2 ]) = min(1,1) = 1 长度3： dp[ 0][ 2]：'a'='a'? 是 → dp[ 1][ 2 ] = 1 dp[ 1][ 3]：'b'='c'? 不 → min(1+dp[ 2][ 3], 1+dp[ 1][ 2 ]) = min(2,2) = 2 长度4：dp[ 0][ 3]：'a'='c'? 不 → min(1+dp[ 1][ 3], 1+dp[ 0][ 2 ]) = min(3,2) = 2 最终结果：dp[ 0][ n-1 ] = 2，表示最少需要2次操作 构造回文方案（回溯）： 从dp[ 0][ 3]=2开始，s[ 0]≠s[ 3]，选择代价较小的dp[ 0][ 2 ]=2 这意味着我们对右端字符进行操作，删除'c'或在左端插入'c' 继续回溯可得到具体操作序列 这个算法的时间复杂度是O(n²)，空间复杂度是O(n²)，可以通过滚动数组优化到O(n)。