题意理解
给定字符串 AAA、BBB、CCC，其中 ∣C∣=∣A∣+∣B∣|C| = |A| + |B|∣C∣=∣A∣+∣B∣。CCC 是由 AAA 和 BBB 交织而成但被修改过的，求最少修改 CCC 中多少个字符才能让 CCC 变成 AAA 和 BBB 的合法交织。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
使用动态规划。
设 dp[i][j]dp[i][j]dp[i][j] 表示：用 AAA 的前 iii 个字符和 BBB 的前 jjj 个字符，交织成 CCC 的前 i+ji+ji+j 个字符，最少需要修改的字符数。
状态转移：
C[i+j−1]C[i+j-1]C[i+j−1] 要么来自 A[i−1]A[i-1]A[i−1]，要么来自 B[j−1]B[j-1]B[j−1]，取最小值：
dp[i][j]=min(dp[i−1][j]+costA,dp[i][j−1]+costB)dp[i][j] = min(dp[i-1][j] + cost_A, dp[i][j-1] + cost_B) dp[i][j]=min(dp[i−1][j]+costA ,dp[i][j−1]+costB )
其中：
* costA=(A[i−1]≠C[i+j−1])cost_A = (A[i-1] \neq C[i+j-1])costA =(A[i−1]=C[i+j−1]) ? 111 : 000
* costB=(B[j−1]≠C[i+j−1])cost_B = (B[j-1] \neq C[i+j-1])costB =(B[j−1]=C[i+j−1]) ? 111 : 000
边界条件：
* dp[0][0]=0dp[0][0] = 0dp[0][0]=0
* dp[i][0]dp[i][0]dp[i][0]：只用 AAA 的前 iii 个字符匹配 CCC 的前 iii 个
* dp[0][j]dp[0][j]dp[0][j]：只用 BBB 的前 jjj 个字符匹配 CCC 的前 jjj 个
答案： dp[∣A∣][∣B∣]dp[|A|][|B|]dp[∣A∣][∣B∣]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
