区间动态规划例题：最小代价构造回文串问题（字符替换与删除） 题目描述 给定一个字符串 s 和两个整数 cost_insert 和 cost_replace ，分别表示插入一个字符和替换一个字符的代价。你可以进行以下操作任意次： 在任意位置插入一个字符，代价为 cost_insert 。 将任意一个字符替换为另一个字符，代价为 cost_replace 。 求将 s 变成回文串的最小总代价。 示例 ： 输入： s = "abac" , cost_insert = 1 , cost_replace = 1 输出： 1 （将 'c' 替换为 'b' ，代价为 1）。 解题过程 1. 定义状态 设 dp[i][j] 表示将子串 s[i:j+1] （即从索引 i 到 j 的子串）变成回文串的最小代价。目标是求 dp[0][n-1] ，其中 n 是字符串长度。 2. 状态转移分析 对于子串 s[i:j+1] ，比较首尾字符 s[i] 和 s[j] ： 情况1 ： s[i] == s[j] 首尾字符已相等，不需要操作，直接处理内部子串： dp[i][j] = dp[i+1][j-1] 。 情况2 ： s[i] != s[j] 需要操作使首尾匹配，有三种策略： 在末尾插入一个与 s[i] 相同的字符 ： 插入后， s[i] 与新增字符匹配，需处理 s[i+1:j+1] ，代价为 cost_insert + dp[i+1][j] 。 在开头插入一个与 s[j] 相同的字符 ： 插入后，新增字符与 s[j] 匹配，需处理 s[i:j] ，代价为 cost_insert + dp[i][j-1] 。 将 s[i] 替换为 s[j] （或反之） ： 替换后首尾相等，需处理内部子串，代价为 cost_replace + dp[i+1][j-1] 。 取三种策略的最小值： dp[i][j] = min(cost_insert + dp[i+1][j], cost_insert + dp[i][j-1], cost_replace + dp[i+1][j-1]) 。 3. 初始化与边界条件 空串或单字符子串已是回文串，代价为 0： dp[i][i] = 0 （单字符）。 长度为 2 的子串 s[i:i+2] ： 若 s[i] == s[i+1] ， dp[i][i+1] = 0 。 否则， dp[i][i+1] = min(cost_replace, 2 * cost_insert) （替换一次或插入两次）。 4. 计算顺序 按子串长度 len 从小到大计算（从 2 到 n ），确保计算 dp[i][j] 时，更短的子串结果已就绪。 5. 示例推导 以 s = "abac" , cost_insert = 1 , cost_replace = 1 为例： 初始化：所有单字符代价为 0， dp[1][2] （子串 "ba" ）的代价为 min(1, 2) = 1 （替换 'a' 为 'b' ）。 计算 dp[0][3] （整个字符串）： s[0]='a' ≠ s[3]='c' ，需比较三种操作： 末尾插入 'a' ：代价 = 1 + dp[1][3] （需计算 dp[1][3] ）。 开头插入 'c' ：代价 = 1 + dp[0][2] 。 替换 'c' 为 'a' ：代价 = 1 + dp[1][2] 。 通过递推得到 dp[1][3] = 1 （子串 "bac" 替换 'c' 为 'b' ）， dp[0][2] = 1 （子串 "aba" 已是回文）。 dp[0][3] = min(1+1, 1+1, 1+1) = 1 。 最终结果为 dp[0][3] = 1 。 6. 算法复杂度 时间复杂度：O(n²)，需要填充 n×n 的 DP 表。 空间复杂度：O(n²)，可优化至 O(n)（仅存储当前行和上一行）。 关键点 通过比较首尾字符，将问题分解为更小的子问题。 插入操作可理解为“跳过”不匹配的字符，替换操作直接修改字符。 实际编码时需注意边界索引（如 i > j 时子串为空，代价为 0）。