cost[a][a]=0, cost[b][d]=1, cost[c][c]=0, 其他替换代价为无穷大（表示不可行）

线性动态规划：最长公共子序列的变种——带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符替换代价表 cost （ cost[a][b] 表示将字符 a 替换为 b 的代价，若 a == b 则代价为 0）。允许对 s1 中的字符进行替换操作（不能删除或插入），目标是找到一个替换方案，使得替换后的 s1 与 s2 的公共子序列长度尽可能长，且替换操作的总代价不超过给定的预算 B 。要求输出满足预算限制的最长公共子序列长度。 解题过程 问题分析 核心目标：在预算限制下最大化公共子序列长度。 关键约束：每次替换操作有特定代价，总代价不能超过 B 。 难点：需要同时跟踪公共子序列长度和累计代价，需在动态规划状态中增加预算维度。 状态定义 设 dp[i][j][k] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符，且总替换代价不超过 k 时的最长公共子序列长度。 i 范围： 0 到 len(s1) j 范围： 0 到 len(s2) k 范围： 0 到 B 状态转移方程 Case 1: 不匹配当前字符 跳过 s1[i] 或 s2[j] ，继承之前的最优解： dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]) Case 2: 匹配 s1[i] 和 s2[j] （需考虑替换代价） 若 s1[i] == s2[j] ，无需替换，代价为 0： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1) 若 s1[i] != s2[j] ，需检查替换代价 c = cost[s1[i]][s2[j]] ： 若 k ≥ c ，则替换可行： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k - c] + 1) 初始化 当 i = 0 或 j = 0 时，公共子序列长度为 0： dp[0][j][k] = 0 ， dp[i][0][k] = 0 （对所有 k ） 计算顺序 按 i 从 0 到 n ， j 从 0 到 m ， k 从 0 到 B 三重循环递推。 答案提取 最终答案为 dp[n][m][B] ，其中 n = len(s1) ， m = len(s2) 。 示例演示 设 s1 = "abc" ， s2 = "adc" ，预算 B = 2 ，代价表如下： 步骤1：初始化 dp[0][j][k] = 0 ， dp[i][0][k] = 0 步骤2：计算 i=1, j=1 （字符 'a' 和 'a'） 匹配成功，代价 0： dp[1][1][k] = 1 （对 k ≥ 0 ） 步骤3：计算 i=2, j=2 （字符 'b' 和 'd'） 替换代价为 1，若 k ≥ 1 ： dp[2][2][k] = max(不匹配结果, dp[1][1][k-1] + 1) = 2 步骤4：计算 i=3, j=3 （字符 'c' 和 'c'） 匹配成功，代价 0： dp[3][3][2] = dp[2][2][2] + 1 = 3 最终答案为 3，总代价为 1（≤ B=2）。 复杂度分析 时间复杂度：O(n × m × B) 空间复杂度：可优化至 O(m × B) 使用滚动数组。