一道典型的 线性 DP 题。
状态定义
像这种线性动态规划，一种常见的状态定义方法是：用 (f_i) 表示 前(i) 个元素满足要求（只考虑前 (i) 个元素）时的最佳答案。
因此我们很自然地想到用 (f(i,j)) 表示将 (A[1..i]) 转换为 (B[1..j]) 所需的最少操作次数，(f(n,m)) 就是问题的答案（(n,m) 分别表示字符串 (A,B) 的长度）。
状态转移
线性 DP 中，状态转移通常只需要考虑 最后一点。
请设想这样一种场景，(A[1..i]) 经过若干次操作被改成了 (B[1..j])，且 最后一步操作是在 (A) 的末尾进行的。我们不由地想到，这最后一步操作只可能是以下三种：
于是我们发现，有三种策略可以把 (A[1..i]) 修改为 (B[1..j])：
状态转移式：
[f(i,j)=\min \left{ \begin{aligned} f(i-1,j) & +1 \ f(i,j-1) & +1 \ f(i-1,j-1) & + \left{ \begin{aligned} 0 & ,\textbf{if }A_i=B_j\ 1 & ,\textbf{if }A_i \neq B_j \end{aligned} \right. \end{aligned} \right. \quad (i>0,j>0) ]
边界条件
观察状态转移式，注意从左往右的 下标变化，下标要么不变，要么变小，因此边界就是下标为 (0) 的时候：
[\begin{aligned} f(0,j) & = j \ f(i,0) & = i \ f(0,0) & = 0 \ \end{aligned} ]
递推顺序
由于从左往右下标要么不变，要么变小，因此递推顺序是从小到大枚举 (i) 和 (j)。
在开始递推之前，应 先求出所有边界的值。
字符串下标从 1 开始。
#include
#include
#include
#include
using namespace std;
const int maxn = 2000 + 5;
char A[maxn];
char B[maxn];
int f[maxn][maxn];
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%s%s", A + 1, B + 1);
int n = strlen(A + 1);
int m = strlen(B + 1);
f[0][0] = 0;
for (int i = 1; i
Original: https://www.cnblogs.com/zhb2000/p/luogu-P2758.html
Author: zhb2000
Title: 洛谷 P2758 编辑距离
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587651/
转载文章受原作者版权保护。转载请注明原作者出处！