线性动态规划：最长公共子序列的变种——带字符替换限制的最长公共子序列（进阶版：允许部分字符替换为通配符） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符替换限制规则：某些字符可以被替换为通配符（用 * 表示，可匹配任意字符），但替换操作有成本。具体来说，每个字符替换为通配符的成本为 1，而直接匹配或通配符匹配的成本为 0。目标是找到两个字符串的一个子序列，使得通过最多进行 k 次字符替换（即替换成本不超过 k ）后，子序列能够完全匹配。你需要计算满足条件的最长子序列的长度。 例如： s1 = "abcde" , s2 = "ace" , k = 1 ：最长子序列为 "ace" ，无需替换，长度为 3。 s1 = "abcde" , s2 = "acf" , k = 1 ：将 s2 的 'f' 替换为通配符后匹配 s1 的 'e' ，子序列 "ace" 长度为 3。 解题过程 步骤 1：定义状态 这是一个带限制的 LCS 变种问题。我们使用动态规划，定义状态 dp[i][j][t] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，使用恰好 t 次替换操作所能得到的最长公共子序列长度。其中： i 的范围是 0 到 len(s1) （ i=0 表示空字符串）。 j 的范围是 0 到 len(s2) 。 t 的范围是 0 到 k （替换次数上限）。 步骤 2：状态转移方程 状态转移基于当前字符的匹配情况： 不选当前字符 ：继承之前的状态。 dp[i][j][t] = max(dp[i][j][t], dp[i-1][j][t], dp[i][j-1][t]) 选当前字符 ：当 s1[i-1] == s2[j-1] 时，直接匹配，成本不变。 dp[i][j][t] = max(dp[i][j][t], dp[i-1][j-1][t] + 1) 使用替换操作 ：当 s1[i-1] != s2[j-1] 但 t > 0 时，可以将其中一个字符替换为通配符（成本为 1），实现匹配。 dp[i][j][t] = max(dp[i][j][t], dp[i-1][j-1][t-1] + 1) 注意：通配符匹配的本质是忽略字符差异，因此替换操作允许不相等字符被视为匹配。 步骤 3：初始化 当 i=0 或 j=0 时，任意 t 下公共子序列长度为 0： dp[0][j][t] = 0 对所有 j, t dp[i][0][t] = 0 对所有 i, t 其他状态初始化为负无穷（或 -1），表示不可达。 步骤 4：计算顺序 按 i 从 0 到 len(s1) ， j 从 0 到 len(s2) ， t 从 0 到 k 的顺序遍历。 步骤 5：答案提取 最终答案是所有 t （ 0 ≤ t ≤ k ）中 dp[len(s1)][len(s2)][t] 的最大值。 举例说明 以 s1 = "abcde" , s2 = "acf" , k = 1 为例： 初始化： dp[0][j][t] = 0 , dp[i][0][t] = 0 。 计算 i=1, j=1 ： s1[0]='a' 匹配 s2[0]='a' ，直接匹配， dp[1][1][0] = 1 。 i=2, j=2 ： s1[1]='b' 不匹配 s2[1]='c' ，但 t=1 时可替换， dp[2][2][1] = dp[1][1][0] + 1 = 2 。 i=3, j=3 ： s1[2]='c' 匹配 s2[2]='f' ？不匹配，但 t=1 时替换 'f' 为通配符匹配 'c' ， dp[3][3][1] = dp[2][2][0] + 1 ？注意 dp[2][2][0] 未定义（因之前需替换），实际应继承 dp[2][2][1] = 2 ，替换后 t=1 已用，但匹配成功，长度变为 3。 最终得到最长子序列长度为 3。 优化点 空间优化：由于 dp[i][j][t] 只依赖于 i-1 和 j-1 ，可滚动数组压缩为二维 dp[j][t] 。 剪枝：当 t > min(i, j) 时无需计算，因为替换次数不可能超过字符数。 通过以上步骤，我们解决了带替换限制的 LCS 问题，核心是在传统 LCS 上增加替换维度的状态管理。