区间动态规划例题：最小成本构造回文串问题（字符插入、删除、替换的通用版本）
题目描述
给定一个字符串 s，你可以进行三种操作：
- 插入一个字符，成本为
insertCost。 - 删除一个字符，成本为
deleteCost。 - 替换一个字符，成本为
replaceCost（若字符相同，替换成本为0）。
要求通过操作将 s 变成回文串，求最小总成本。
解题思路
1. 定义状态
设 dp[i][j] 表示将子串 s[i:j]（左闭右闭区间）变为回文串的最小成本。
2. 状态转移
考虑子串的两端字符 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]和新增字符匹配），成本为insertCost + dp[i+1][j]。 - 删除开头的
s[i]（让内部子串与s[j]匹配），成本为deleteCost + dp[i+1][j]。 - 将
s[i]替换为s[j]（或反之），成本为replaceCost + dp[i+1][j-1]。
取三种策略的最小值：
dp[i][j] = min(insertCost + dp[i+1][j], deleteCost + dp[i+1][j], replaceCost + dp[i+1][j-1])。 - 在末尾插入一个与
3. 边界条件
-
空串或单字符已是回文，成本为0：
dp[i][i] = 0（单字符）。
dp[i][i-1] = 0（空串，当i > j时视为空串，但本题i <= j）。 -
长度为2的子串：
若s[i] == s[i+1]，dp[i][i+1] = 0；
否则dp[i][i+1] = min(replaceCost, insertCost + deleteCost, ...)（需比较所有操作）。
逐步计算示例
设 s = "abc"，insertCost = 1, deleteCost = 1, replaceCost = 1。
步骤1：初始化
dp[0][0] = dp[1][1] = dp[2][2] = 0（单字符成本为0）。
步骤2：计算长度为2的子串
-
s[0:1] = "ab"：- 替换：将
a改为b（或b改为a），成本=1 +dp[1][0]（空串成本0）=1。 - 插入：在末尾插入
a，成本=1 +dp[0][0]=1；或删除a，成本=1 +dp[1][1]=1。 - 最小成本
dp[0][1] = min(1, 1, 1) = 1。
- 替换：将
-
s[1:2] = "bc"：同理dp[1][2] = 1。
步骤3：计算长度为3的子串 s[0:2] = "abc"
- 两端
s[0]='a'!=s[2]='c'：- 插入：在末尾插入
a，成本=1 +dp[1][2]=1+1=2。 - 删除：删除开头的
a，成本=1 +dp[1][2]=2。 - 替换：将
a改为c，成本=1 +dp[1][1]=1+0=1。
dp[0][2] = min(2, 2, 1) = 1。
- 插入：在末尾插入
最终最小成本为 dp[0][2] = 1（将 a 替换为 c 得到 "cbc"）。
算法实现要点
- 按子串长度从小到大计算
dp[i][j]。 - 注意边界处理（
i > j时成本为0，但循环中i <= j）。 - 时间复杂度 O(n²)，空间复杂度 O(n²)。
此方法通用性强，可通过调整成本值适应不同场景。