区间动态规划例题：最小插入次数构造回文串问题（带字符替换成本） 题目描述 给定一个字符串 s 和一个长度为 26 的整数数组 cost ，其中 cost[i] 表示将任意字符替换为字符 'a' + i 的成本。你可以对字符串进行两种操作： 插入一个字符，成本为 insertCost （固定值）。 替换一个字符，成本为 cost[newChar - 'a'] 。 目标是通过若干次操作将 s 变成回文串，且总成本最小。求最小成本。 解题思路 这是一个区间动态规划问题。定义 dp[i][j] 表示将子串 s[i..j] 变成回文串的最小成本。我们考虑子串两端字符 s[i] 和 s[j] 的情况，逐步缩小区间。 详细步骤 状态定义 dp[i][j] ：将子串 s[i..j] 变成回文串的最小成本。 基础情况：当 i == j 时，单个字符本身就是回文，成本为 0。 当 i > j 时，空串成本为 0。 状态转移方程 对于区间 [i, j] ，考虑两端字符 s[i] 和 s[j] ： 情况1 ：如果 s[i] == s[j] ，两端字符已匹配，直接处理内部子串 [i+1, j-1] ： \[ dp[ i][ j] = dp[ i+1][ j-1 ] \] 情况2 ：如果 s[i] != s[j] ，有三种策略使两端匹配： a. 在末尾插入一个与 s[i] 相同的字符 ：成本为 insertCost + dp[i+1][j] 。 b. 在开头插入一个与 s[j] 相同的字符 ：成本为 insertCost + dp[i][j-1] 。 c. 替换一端字符 ： 将 s[i] 替换为 s[j] ，成本为 cost[s[j] - 'a'] + dp[i+1][j-1] 。 将 s[j] 替换为 s[i] ，成本为 cost[s[i] - 'a'] + dp[i+1][j-1] 。 取以上四种情况的最小值： \[ dp[ i][ j ] = \min\left( \text{insertCost} + dp[ i+1][ j ], \text{insertCost} + dp[ i][ j-1 ], \text{cost}[ s[ j] - 'a'] + dp[ i+1][ j-1 ], \text{cost}[ s[ i] - 'a'] + dp[ i+1][ j-1 ] \right) \] 初始化与计算顺序 初始化：所有 dp[i][i] = 0 ，空区间 dp[i][j] = 0 (i > j) 。 计算顺序：按区间长度 len 从小到大的顺序计算， len 从 2 到 n 。 最终答案 答案为 dp[0][n-1] ，即将整个字符串变为回文的最小成本。 示例演示 设 s = "ab" ， insertCost = 1 ， cost = [1, 2, ...] （ cost[0] 对应 'a'， cost[1] 对应 'b'）。 区间 [0,1] ： s[0]='a' ， s[1]='b' ，不匹配。 插入：在末尾插入 'a'，成本=1 + dp[0][0] =1+0=1；在开头插入 'b'，成本=1 + dp[1][1] =1+0=1。 替换：将 'a' 改为 'b'，成本=2 + dp[1][0] =2+0=2；将 'b' 改为 'a'，成本=1 + dp[1][0] =1+0=1。 最小值 = min(1, 1, 2, 1) = 1。 最终最小成本为 1（例如将 'b' 替换为 'a'，得到 "aa"）。 总结 本题通过区间动态规划，综合考虑插入和替换操作的成本，逐步将子串变为回文。关键点在于对两端字符不匹配时的多种策略进行对比，选择成本最小的路径。