最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价，且允许部分字符替换为通配符） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符替换代价表 cost ，其中 cost[a][b] 表示将字符 a 替换为 b 的代价（若替换不允许，则代价为无穷大）。此外，允许将部分字符替换为通配符 * （通配符可匹配任意字符），替换代价为固定值 C 。要求找到 s1 和 s2 的一个公共子序列，但允许对子序列中的字符进行替换操作（包括替换为通配符），使得替换操作的总代价最小，且最终子序列相同。输出最小代价。 关键点 子序列需保持原顺序，但字符可替换。 通配符 * 可匹配任意字符，但使用时有固定代价。 目标是最小化总替换代价。 解题步骤 1. 定义状态 设 dp[i][j] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，达成公共子序列的最小替换代价。 2. 状态转移方程 分为以下情况： 直接匹配 ：若 s1[i-1] == s2[j-1] ，则无需替换，直接继承状态： dp[i][j] = dp[i-1][j-1] 字符替换 ：若 s1[i-1] != s2[j-1] ，可尝试将 s1[i-1] 替换为 s2[j-1] （代价为 cost[s1[i-1]][s2[j-1]] ），或将 s2[j-1] 替换为 s1[i-1] （代价为 cost[s2[j-1]][s1[i-1]] ）： dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost[s1[i-1]][s2[j-1]], dp[i-1][j-1] + cost[s2[j-1]][s1[i-1]]) 使用通配符 ：可将 s1[i-1] 替换为 * （代价 C ）或 s2[j-1] 替换为 * （代价 C ），此时 * 可匹配任意字符： dp[i][j] = min(dp[i][j], dp[i-1][j] + C, dp[i][j-1] + C) 跳过字符 ：可跳过 s1[i-1] 或 s2[j-1] （相当于不将其纳入子序列），但需注意跳过本质是删除操作，此题中删除无代价？ — 澄清：本题聚焦替换代价，跳过字符（删除）通常无代价，但需明确是否允许。若允许，则： dp[i][j] = min(dp[i][j], dp[i-1][j], dp[i][j-1]) 3. 初始化 dp[0][0] = 0 ：两个空字符串无代价。 dp[i][0] ：将 s1 的前 i 个字符全部删除或替换为通配符的代价。若允许删除无代价，则 dp[i][0] = 0 ；若必须通过通配符处理，则 dp[i][0] = i * C 。 同理处理 dp[0][j] 。 4. 最终答案 答案为 dp[len(s1)][len(s2)] 。 举例说明 设 s1 = "abc" , s2 = "adc" , cost 表： cost['b']['d'] = 2 , cost['d']['b'] = 3 （其他替换不允许，代价无穷大） 通配符代价 C = 1 DP 表计算 （允许删除无代价）： 初始化： dp[0][0]=0 , dp[i][0]=0 , dp[0][j]=0 i=1,j=1 ： s1[0]=='a' , s2[0]=='a' ，匹配， dp[1][1]=0 i=1,j=2 ： 'a' vs 'd' ，不匹配，考虑替换（不允许）、通配符或跳过： 跳过 s2 的 'd' ： dp[1][2] = dp[1][1] = 0 i=2,j=1 ： 'b' vs 'a' ，类似地，跳过 s1 的 'b' ， dp[2][1]=0 i=2,j=2 ： 'b' vs 'd' 替换： cost['b']['d']=2 ， dp[2][2] = dp[1][1] + 2 = 2 通配符： dp[2][2] = min(dp[2][1]+1=1, dp[1][2]+1=1) = 1 跳过： min(dp[1][2]=0, dp[2][1]=0) = 0 取最小 0 继续计算至 dp[3][3] ，最终得到最小代价。 复杂度分析 时间复杂度：O(nm)，其中 n、m 为字符串长度。 空间复杂度：可优化至 O(min(n, m))。 关键思考 通配符的引入增加了灵活性，但需权衡固定代价。 若替换代价过高，可能优先选择通配符或跳过字符。 初始化方式需根据问题要求调整（删除是否有代价）。