最小成本回文串构造问题（字符插入与删除） 题目描述 给定一个字符串s，你可以在任意位置插入或删除字符，每次操作的成本可能不同（插入和删除的成本可能不同）。你的目标是通过一系列插入和删除操作，将字符串s变成回文串，并且总成本最小。要求设计一个算法，计算最小成本。 解题过程 问题分析 我们需要将任意字符串转换为回文串，允许的操作包括插入和删除。每个字符的插入和删除成本可能不同（例如，插入字符'a'的成本为 insert_cost['a'] ，删除字符'a'的成本为 delete_cost['a'] ）。关键在于如何选择操作序列，使得总成本最小。 定义状态 设 dp[i][j] 表示将子串 s[i..j] （包含i和j）转换为回文串的最小成本。目标是计算 dp[0][n-1] ，其中n是字符串长度。 状态转移方程 考虑子串 s[i..j] ： 如果 s[i] == s[j] ，则两端字符已经匹配，不需要额外操作，直接递归处理内部子串： dp[i][j] = dp[i+1][j-1] 。 如果 s[i] != s[j] ，则需要通过插入或删除操作使两端匹配，有两种选择： a. 删除s[ i] ：成本为 delete_cost[s[i]] + dp[i+1][j] （删除左端字符后，处理剩余子串）。 b. 在j右侧插入s[ i] ：成本为 insert_cost[s[i]] + dp[i+1][j] （等效于在右端添加匹配字符）。 c. 删除s[ j] ：成本为 delete_cost[s[j]] + dp[i][j-1] 。 d. 在i左侧插入s[ j] ：成本为 insert_cost[s[j]] + dp[i][j-1] 。 取这四种情况的最小值： dp[i][j] = min(delete_cost[s[i]] + dp[i+1][j], insert_cost[s[i]] + dp[i+1][j], delete_cost[s[j]] + dp[i][j-1], insert_cost[s[j]] + dp[i][j-1]) 。 边界条件 当 i > j 时，子串为空，已经是回文，成本为0： dp[i][j] = 0 。 当 i == j 时，单字符本身是回文，成本为0： dp[i][j] = 0 。 计算顺序 由于 dp[i][j] 依赖于 dp[i+1][j] 、 dp[i][j-1] 和 dp[i+1][j-1] ，需要按子串长度从小到大计算：先计算所有长度为1的子串，然后长度为2，依此类推，直到整个字符串。 示例 假设字符串s = "abac"，插入和删除成本均为1（简化情况）。 初始化：所有单字符子串成本为0。 长度2子串： "ab"：两端不匹配，最小成本为min(删除'a'+成本"b", 插入'a'+成本"b", 删除'b'+成本"a", 插入'b'+成本"a") = min(1+0, 1+0, 1+0, 1+0) = 1。 类似计算其他长度子串，最终得到 dp[0][3] 即为最小成本。 优化与变体 如果插入和删除成本对称（例如成本相同），可简化为仅考虑删除或插入。实际编码时需注意索引边界，避免重复计算。 通过以上步骤，可系统求解最小成本回文串构造问题。