区间动态规划例题：最小成本生成目标子序列问题（允许字符插入、删除、替换，且操作有不同成本，求从源字符串通过操作得到目标字符串指定子序列的最小总成本） 题目描述 给定两个字符串 source 和 target ，以及三个整数 insertCost 、 deleteCost 和 replaceCost ，分别表示插入、删除、替换一个字符的成本。 你可以对源字符串 source 进行任意次操作，每次操作可以选择： 在任意位置插入一个字符（成本为 insertCost ）。 删除任意位置的字符（成本为 deleteCost ）。 将任意位置的字符替换为另一个字符（成本为 replaceCost ）。 目标是使得 source 最终变为一个字符串，该字符串包含 target 作为其 子序列 （注意：不是连续子串，而是子序列）。 换句话说，你需要通过操作使得 target 中的字符按顺序出现在结果字符串中（可以不连续）。 求达成目标的最小总成本。 示例 假设： source = "abc" target = "ac" insertCost = 1 deleteCost = 1 replaceCost = 2 一种最优方案： 删除 source 中的第二个字符 'b' （成本 1），得到 "ac" ，此时 "ac" 包含子序列 "ac" （就是它自己）。 总成本 = 1。 解题思路 这是一个区间动态规划问题，但需要结合 序列匹配 的思想。我们可以定义状态 dp[i][j] 表示： 将 source 的前 i 个字符（即 source[0..i-1] ）进行操作，使其包含 target 的前 j 个字符（即 target[0..j-1] ）作为子序列的最小成本。 这里 i 的范围是 0..n （ n = source.length ）， j 的范围是 0..m （ m = target.length ）。 最终答案是 dp[n][m] 。 状态转移分析 考虑如何从 dp[i-1][*] 或 dp[i][j-1] 转移到 dp[i][j] 。我们面对的是 source 的第 i 个字符（ source[i-1] ）和 target 的第 j 个字符（ target[j-1] ）。 目标是让 target[0..j-1] 成为子序列，所以我们需要决定如何处理 source[i-1] 以及如何匹配 target[j-1] 。 状态转移方程 删除 source[i-1] 直接删除 source 的第 i 个字符，成本为 deleteCost ，然后前 i-1 个字符需要包含 target[0..j-1] 作为子序列。 所以： dp[i][j] = dp[i-1][j] + deleteCost 。 保留 source[i-1] 并匹配某个目标字符 如果 source[i-1] == target[j-1] ，那么我们可以让 source[i-1] 匹配 target[j-1] ，此时前 i-1 个字符只需要包含 target[0..j-2] 作为子序列即可。 所以： dp[i][j] = dp[i-1][j-1] （无需额外成本）。 如果 source[i-1] != target[j-1] ，我们可以 替换 source[i-1] 为 target[j-1] ，成本为 replaceCost ，然后前 i-1 个字符需要包含 target[0..j-2] 作为子序列。 所以： dp[i][j] = dp[i-1][j-1] + replaceCost 。 插入 target[j-1] 我们可以在 source[0..i-1] 的末尾 插入 字符 target[j-1] ，成本为 insertCost ，这样插入后新字符匹配 target[j-1] ，而前 i 个字符（原来的 source[0..i-1] ）需要包含 target[0..j-2] 作为子序列。 注意：插入操作并不消耗 source 的字符，所以 i 不变， j 减少。 所以： dp[i][j] = dp[i][j-1] + insertCost 。 初始化 dp[0][0] = 0 ：空源字符串包含空目标子序列，成本为0。 对于 i > 0, j = 0 ：目标子序列为空，我们只需要删除 source 的所有前 i 个字符即可，所以 dp[i][0] = i * deleteCost 。 对于 i = 0, j > 0 ：源字符串为空，要包含 target[0..j-1] 作为子序列，必须插入全部 j 个字符，所以 dp[0][j] = j * insertCost 。 计算顺序 由于 dp[i][j] 依赖于 dp[i-1][j] 、 dp[i][j-1] 和 dp[i-1][j-1] ，我们可以按 i 从 0 到 n ， j 从 0 到 m 的顺序计算。 最终答案 dp[n][m] 即为最小总成本。 举例演算 以示例数据： source = "abc" , target = "ac" , insertCost = 1 , deleteCost = 1 , replaceCost = 2 。 n=3 , m=2 。 初始化： dp[0][0]=0 , dp[1][0]=1 , dp[2][0]=2 , dp[3][0]=3 dp[0][1]=1 , dp[0][2]=2 计算 dp[1][1] （ i=1 , j=1 , 对应字符 'a' , 'a' ）： 删除： dp[0][1]+1=1+1=2 匹配（相等）： dp[0][0]=0 插入： dp[1][0]+1=1+1=2 取最小值得 dp[1][1]=0 。 计算 dp[1][2] （ i=1 , j=2 , 字符 'a' , 'c' ）： 删除： dp[0][2]+1=2+1=3 替换（不等）： dp[0][1]+2=1+2=3 插入： dp[1][1]+1=0+1=1 取最小值得 dp[1][2]=1 。 计算 dp[2][1] （ i=2 , j=1 , 字符 'b' , 'a' ）： 删除： dp[1][1]+1=0+1=1 替换（不等）： dp[1][0]+2=1+2=3 插入： dp[2][0]+1=2+1=3 取最小值得 dp[2][1]=1 。 计算 dp[2][2] （ i=2 , j=2 , 字符 'b' , 'c' ）： 删除： dp[1][2]+1=1+1=2 替换（不等）： dp[1][1]+2=0+2=2 插入： dp[2][1]+1=1+1=2 取最小值得 dp[2][2]=2 。 计算 dp[3][1] （ i=3 , j=1 , 字符 'c' , 'a' ）： 删除： dp[2][1]+1=1+1=2 替换（不等）： dp[2][0]+2=2+2=4 插入： dp[3][0]+1=3+1=4 取最小值得 dp[3][1]=2 。 计算 dp[3][2] （ i=3 , j=2 , 字符 'c' , 'c' ）： 删除： dp[2][2]+1=2+1=3 匹配（相等）： dp[2][1]=1 插入： dp[3][1]+1=2+1=3 取最小值得 dp[3][2]=1 。 所以最终答案为 dp[3][2] = 1 ，与示例一致。 算法复杂度 时间复杂度：O(n × m)，空间复杂度可优化为 O(m) 通过滚动数组。 核心总结 本题将编辑距离问题与 子序列包含 条件结合，状态定义巧妙转化为“source 的前 i 个字符包含 target 的前 j 个字符作为子序列”。转移时考虑删除、替换/匹配、插入三种操作，取最小成本。通过动态规划可高效求解。