E. Three Strings 超清晰题解

这道题是经典双序列合并 DP，代码极简、思路清晰，是字符串 DP 的入门好题。

一、先把题目读懂

给你三个字符串 $a, b, c$：

1. $c$ 原本应该是：从 $a$ 头部、$b$ 头部交替取字符拼成（保持 $a$、$b$ 内部顺序不变）
2. 然后有人修改了一些字符，变成了现在的 $c$
3. 问：最少改了多少个字符？

等价问法： 在所有合法的 $a+b$ 合并序列中，找到和当前 $c$ 匹配最多的那个，答案就是 总长度 - 最大匹配数（也就是你的代码直接算的最小修改数）。

二、核心 DP 状态定义

f[i][j]

表示： 从 $a$ 取前 $i$ 个字符，从 $b$ 取前 $j$ 个字符，合并成的串，和 $c$ 前 $i+j$ 个字符匹配的最小修改次数。

✅ 目标：f[n][m]（$n=a$ 长度，$m=b$ 长度）

三、转移方程（最关键）

每个状态 f[i][j] 只有 2 种来源：

1. 最后一个字符来自 a

• 说明：用了 $a$ 的第 $i$ 个字符（$a[i-1]$）
• 放在 $c$ 的第 $i+j-1$ 位
• 代价：a[i-1] != c[i+j-1]（不等就是 1，相等就是 0）
• 转移：

  f[i-1][j] + (a[i-1] != c[i+j-1])
  

2. 最后一个字符来自 b

• 说明：用了 $b$ 的第 $j$ 个字符（$b[j-1]$）
• 放在 $c$ 的第 $i+j-1$ 位
• 代价：b[j-1] != c[i+j-1]
• 转移：

  f[i][j-1] + (b[j-1] != c[i+j-1])
  

最终转移

f[i][j] = min(来自a, 来自b);

四、边界条件

1. i=0, j=0：空串，修改次数 = 0
2. i=0：只用 b，一路匹配

   f[0][j] = f[0][j-1] + (b[j-1] != c[j-1])
   

3. j=0：只用 a，一路匹配

   f[i][0] = f[i-1][0] + (a[i-1] != c[i-1])
   

五、代码逐行精讲

#include <iostream>
using namespace std;

const int N = 1e3 + 5;
int f[N][N];  // DP 数组，i<=1e3, j<=1e3 完全够用

int main()
{
	int T;
	cin >> T;
	while (T--)  // 多组测试用例
	{
		string a, b, c;
		cin >> a >> b >> c;
		int n = a.size(), m = b.size();
		
		// 初始化 DP 数组为 0
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				f[i][j] = 0;
		
		// 开始 DP 转移
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
			{
				if (i == 0 && j == 0) continue;  // 初始状态跳过
                
				// 只从 b 转移
				else if (i == 0) 
					f[i][j] = f[i][j - 1] + (b[j - 1] != c[j - 1]);
                
				// 只从 a 转移
				else if (j == 0) 
					f[i][j] = f[i - 1][j] + (a[i - 1] != c[i - 1]);
                
				// 从 a 或 b 里选代价更小的
				else 
					f[i][j] = min(
						f[i - 1][j] + (a[i - 1] != c[i + j - 1]), 
						f[i][j - 1] + (b[j - 1] != c[i + j - 1])
					);
			}
		cout << f[n][m] << "\n";
	}
	return 0;
}

六、复杂度（完美通过题目限制）

• 时间：$O(nm)$
• $n,m \le 10^3$ → $1e6$ 每次
• $t \le 1e3$，但总和 $\sum n,\sum m \le 2e3$
• 实际总运算量 < 4e6，稳过

七、一句话总结

这道题就是： 用 DP 枚举所有合法的 a、b 合并方式，计算每种方式和 c 的最小修改次数，取最小值。

你的代码 完全正确、最优、简洁，是这道题的标准解法 ✅