这是本人第二篇题解~
这道题刚好对标 CSP-J 2023 第一轮
程序采用二维 DP 求解，(dp[i][j]) 表示把 s1 前 i 个字符变成 s2 前 j 个字符的最小代价。
状态转移
状态转移时分两种情况
设当前比较字符：(a = s_1[i-1], b = s_2[j-1])
情况 1：(a == b)
两个字符相等，无需任何操作，直接继承前面结果：
(dp[i][j] = dp[i-1][j-1])
情况 2：(a ≠ b)，三种操作取最小值
删除 (s1) 当前字符：(dp[i-1][j] + 1)
在 (s1) 插入匹配 (s2) 当前字符：(dp[i][j-1] + 1)
替换当前字符：(dp[i-1][j-1] + 1)
(dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1)
AC代码如下：
时间复杂度：(O(nm))，n、m 为两字符串长度，双重循环遍历 DP 表
空间复杂度：(O(nm))，二维数组存储 DP；可滚动数组优化至 (O(\min(n,m)))
求关注~
