最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价，且允许部分字符替换为通配符，同时限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符替换代价表 cost （ cost[a][b] 表示将字符 a 替换为 b 的代价，若为无穷大则禁止替换）。部分字符可替换为通配符 * （匹配任意字符），代价为固定值 c_wild 。此外，某些字符被标记为"必须连续出现"（例如，若 s1 中的字符 'x' 被标记，则 'x' 在公共子序列中必须连续出现至少 k 次）。求满足条件的最长公共子序列，且总替换代价最小。 解题过程 问题分析 核心目标：在字符替换、通配符使用和连续出现限制下，找到最长公共子序列并最小化替换代价。 难点：多重约束（替换代价、通配符、连续字符要求）需在动态规划状态中同时考虑。 状态设计 定义五维DP数组： dp[i][j][cnt][last][flag] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，当前连续字符 last 已出现 cnt 次， flag 表示是否正在匹配一个连续段（0：未开始，1：进行中）。 i ： s1 的指针（0 ≤ i ≤ len(s1)）。 j ： s2 的指针（0 ≤ j ≤ len(s2)）。 cnt ：当前连续字符的计数（0 ≤ cnt ≤ k）。 last ：上一个匹配的字符（用整数表示，0表示尚未匹配任何字符）。 flag ：是否处于连续匹配段（0或1）。 状态转移 字符匹配（不替换） ：若 s1[i] == s2[j] ，直接匹配，更新连续计数： 若 last == s1[i] ： cnt_new = cnt + 1 （连续计数增加）。 否则： cnt_new = 1 （重新开始计数）。 转移代价为0。 字符替换 ：若 cost[s1[i]][s2[j]] 非无穷大，支付代价完成匹配，连续计数更新同上。 使用通配符 ：支付代价 c_wild ，将 s1[i] 或 s2[j] 替换为 * 实现匹配，连续计数重置（通配符中断连续性）。 跳过字符 ：跳过 s1[i] 或 s2[j] ，连续计数重置为0。 连续字符检查 ：若 cnt == k 且 last 被标记为必须连续，允许结束连续段（ flag 置0）。 初始化与结果提取 初始化： dp[0][0][0][0][0] = 0 ，其余为无穷大。 结果：遍历所有 i, j, cnt, last, flag ，取 dp[i][j][cnt][last][flag] 的最小值，且要求 flag=0 （所有连续段已满足）。 关键点 通过五维状态同时跟踪匹配进度、连续计数和段状态，确保约束被满足。 通配符和替换代价在转移时作为可选操作，通过比较代价最小化总成本。 时间复杂度 O(n²·k·|Σ|·2)，需优化状态空间（如滚动数组）。