【动态规划】区间dp：编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A 中的某个字符删除。
2. 插入–在字符串 A 的某个位置插入某个字符。
3. 替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A变为 B 至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

dp[i][j]: A[1~i]变成B[1~j]的最少操作次数

考虑对A[i]的操作：有三种情况。

(1)删除：如果想要删除掉a[i]后，AB匹配，那么就必须先做到A[1~i-1]和B[1~j]匹配

dp[i][j]=dp[i-1][j]+1（删除操作算1次操作）

(2)增加：如果想要在a[i]后增加一个字符后，AB匹配，那么就必选先做到A[1~i]和B[1~j-1]匹配

dp[i][j]=dp[i][j-1]+1（增加操作算1次操作）

(3)修改：如果想要修改a[i]后，AB匹配，那么就必须先做到A[1~i-1]和B[1~j-1]匹配，但是如果A[i]==B[j]的话，就不需要去修改

dp[i][j]=dp[i-1][j-1]+1或0

初始化:

dp[i][0]=i;

dp[0][i]=i;

#include
using namespace std;
int n;
int m;
const int N=1010;
char A[N],B[N];
int dp[N][N];
string s1,s2;
int main(){
    cin>>n;
    cin>>s1;
    cin>>m;
    cin>>s2;
    for(int i=0;i