最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价，且允许部分字符替换为通配符，同时限制某些字符必须连续出现） 问题描述 给定两个字符串s和t，以及一个字符替换代价表。你可以在s或t中执行以下操作： 插入字符（代价固定） 删除字符（代价固定） 替换字符（代价由替换代价表决定） 将某些特定字符替换为通配符（有特殊代价） 此外，要求最终得到的公共子序列中，某些特定字符必须连续出现至少k次。 求使两个字符串相等的最小总代价。 解题过程 步骤1：理解问题核心 这个问题结合了多个复杂要素： 带权编辑距离（不同操作有不同代价） 通配符匹配（某些字符可变为通配符） 字符连续出现限制 我们需要找到一个公共子序列，满足特定字符的连续性要求，且转换代价最小。 步骤2：定义状态 定义 dp[i][j][c][cnt] 表示考虑s的前i个字符和t的前j个字符，当前已匹配的最后一个字符是c，且该字符已连续出现cnt次时的最小代价。 由于状态空间可能很大，我们需要优化： 只对需要连续出现的字符记录连续次数 对其他字符，连续次数记录为1即可 步骤3：状态转移方程 对于每个状态 dp[i][j][c][cnt] ，考虑下一步操作： 情况1：匹配s[ i]和t[ j] 如果 s[i] == t[j] ： 如果 s[i] == c ： dp[i][j][c][cnt] = min(dp[i][j][c][cnt], dp[i-1][j-1][c][cnt-1]) 否则： dp[i][j][s[i]][1] = min(dp[i][j][s[i]][1], dp[i-1][j-1][c][cnt] + 0) 如果 s[i] != t[j] ，但可以替换： 计算替换代价，更新对应状态 情况2：删除s[ i] dp[i][j][c][cnt] = min(dp[i][j][c][cnt], dp[i-1][j][c][cnt] + delete_cost) 情况3：删除t[ j] dp[i][j][c][cnt] = min(dp[i][j][c][cnt], dp[i][j-1][c][cnt] + delete_cost) 情况4：将字符替换为通配符 对于允许替换为通配符的字符： dp[i][j][wildcard][1] = min(dp[i][j][wildcard][1], dp[i-1][j-1][c][cnt] + wildcard_cost) 步骤4：处理连续出现限制 在状态转移过程中，需要检查连续出现限制： 当遇到需要连续出现k次的字符时，只有连续次数≥k的状态才被认为是有效的 可以在状态转移完成后，对不满足连续性要求的状态进行标记或忽略 步骤5：初始化 dp[0][0][*][0] = 0 （空字符串匹配空字符串） 其他状态初始化为无穷大 步骤6：最终答案 最终答案是所有 dp[len(s)][len(t)][c][cnt] 中满足连续性要求的最小值。 复杂度分析 时间复杂度：O(n×m×|Σ|×K)，其中|Σ|是字符集大小，K是最大连续次数限制 空间复杂度：O(n×m×|Σ|×K) 这个算法通过多维动态规划同时处理了字符匹配、代价计算和连续性约束，是编辑距离问题的综合扩展。