线性动态规划：最长公共子序列的变种——带字符替换限制的最长公共子序列（进阶版：允许部分字符替换为通配符） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符替换规则：允许将 s1 中的某些字符替换为通配符 * （通配符可以匹配 s2 中的任意字符，但每个通配符只能匹配一个字符）。同时，限制最多只能进行 k 次替换操作。目标是找到最长的公共子序列（LCS），使得在替换次数不超过 k 的前提下，子序列的长度最大化。 例如： s1 = "abcde" , s2 = "ace" , k = 1 解释：不替换时 LCS 为 "ace"（长度 3）。若将 s1 中的 'b' 替换为 * ，则 s1 变为 "a*cde" ，可与 s2 匹配子序列 "ace"，长度仍为 3。但若允许更多替换，可能匹配更长序列？本例中无需更多替换。 解题思路 在经典 LCS 动态规划基础上，增加状态维度 r 表示已使用的替换次数。定义 dp[i][j][r] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，使用不超过 r 次替换的最长公共子序列长度。 状态转移方程 字符匹配 （ s1[i-1] == s2[j-1] ）： 直接继承前状态并增加长度： dp[i][j][r] = max(dp[i][j][r], dp[i-1][j-1][r] + 1) 字符不匹配 ： 不替换 ：跳过 s1 或 s2 的当前字符： dp[i][j][r] = max(dp[i-1][j][r], dp[i][j-1][r]) 替换 （若 r > 0 ）：将 s1[i-1] 替换为 * 以匹配 s2[j-1] ： dp[i][j][r] = max(dp[i][j][r], dp[i-1][j-1][r-1] + 1) 边界条件 ： 当 i = 0 或 j = 0 时， dp[i][j][r] = 0 （空字符串无公共子序列）。 逐步计算示例 设 s1 = "abc" , s2 = "ac" , k = 1 ，构建 dp 表（ i, j 从 1 开始， r 从 0 到 k ）： 初始化 ：所有 dp[0][j][r] = 0 和 dp[i][0][r] = 0 。 计算 i=1, j=1 （字符 'a' 匹配）： r=0 ： dp[1][1][0] = dp[0][0][0] + 1 = 1 r=1 ： dp[1][1][1] = 1 （同 r=0 ） 计算 i=1, j=2 （'a' 与 'c' 不匹配）： r=0 ：只能跳过字符， dp[1][2][0] = max(dp[0][2][0], dp[1][1][0]) = max(0,1) = 1 r=1 ：可替换 'a' 为 * 匹配 'c'： dp[1][2][1] = max(dp[0][1][0]+1, dp[0][2][1], dp[1][1][1]) = max(1,0,1) = 1 计算 i=2, j=1 （'b' 与 'a' 不匹配）：类似步骤 3，结果对称。 关键步骤 i=2, j=2 （'b' 与 'c' 不匹配）： r=0 ：跳过字符， dp[2][2][0] = max(dp[1][2][0], dp[2][1][0]) = max(1,1) = 1 r=1 ： 不替换： max(dp[1][2][1], dp[2][1][1]) = 1 替换 'b' 为 * ： dp[1][1][0] + 1 = 2 最终 dp[2][2][1] = 2 （通过替换得到 "a* " 和 "ac" 的公共子序列 "ac"） 最终答案 ： dp[len(s1)][len(s2)][k] 即 dp[3][2][1] = 2 （示例中最大长度为 2）。 复杂度分析 时间复杂度：O(n·m·k)，其中 n 和 m 为字符串长度。 空间复杂度：可优化至 O(m·k) 通过滚动数组。 总结 通过增加替换次数的状态维度，将经典 LCS 问题扩展为支持有限字符替换的变种，适用于需容忍部分噪声的序列匹配场景（如基因序列比对）。