①题目描述

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
1.删除–将字符串A中的某个字符删除。
2.插入–在字符串A的某个位置插入某个字符。
3.替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将 A变为B至少需要进行多少次操作。

输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例:
4

②最优子结构分析

我们考虑: 将字符串A的前i个字符构成的子串变成字符串B的前j个字符构成的子串所需的最少的操作次数f[i][j]这个问题;(这里的操作次数不仅仅代表了次数这个数，同时背后隐含了相应将A的子串变成B的子串的进行的对应次数的操作)
对字符串A的最后一个字符A[i]进行的操作的情况进行讨论:

情况一: 将A的前i个字符的最后一个字符A[i]删除后变成B的前j个字符所需的最少操作次数 -- f[i-1][j] + 1;
        (将A[i]删除对应一次操作，然后在将删除后的A的前i-1个字符变成B的前j个字符所需的最少操作次数为f[i-1][j],故该情况下的最少操作次数为f[i-1][j]+1)

情况二: 在A的前i个字符的最后一个字符A[i]后插入一个字符变成B的前j个字符所需的最少操作次数 -- f[i][j-1] + 1;
        (由于在A[i]后插入一个字符后可以将A的前i个字符和插入的这个字符构成的新的子串变成B的前j个字符，故该字符一定是B[j]； 
         于是先要求得将A的前i个字符变成B的前j-1个字符所需的最少操作次数f[i][j-1],再加上插入该字符的一次操作所得该情况下的最少操作次数为f[i][j-1]+1)

情况三: 将A[i]仅替换成某个字符将A的前i个字符变成B的前j个字符(即替换后对A[i]不进行其他任何操作，即A[i]和B[j]的状态已经锁定)，
        此时A[i]替换成的字符必然是B[j]；
        (由于仅替换，故若该字符不是B[j]，替换后无论i是否等于j都会带来在A[i]后进行一定的插入操作，可以对i和j的大小以及所替换的字符(B的前j-1个字符或者是其他字符)
         进行讨论共6种情况，故如果发生替换该字符一定是B[j])
        于是这时候我们需要考虑是否要对该字符进行替换成B[j],即对A[i]和B[j]的情况进行一次讨论：

         (Ⅰ)：若A[i] == B[j]，则不需要考虑替换，此时问题转换成了将A的前i-1个字符变成B的前j-1个字符的最少操作次数f[i-1][j-1]；

         (Ⅱ)：若A[i] != B[j]，则考虑替换，替换后问题转换成了将A的前i-1个字符变成B的前j-1个字符所需的最少操作次数f[i-1][j-1];
               总的最少操作次数为f[i-1][j-1] + 1

③状态表示:

     f[i][j]表示将字符串A的前i个字符构成的子串变成字符串B的前j个字符构成的子串所需的最少的操作次数;

④状态转移:

    ---初始化(先初始化二维数组的两个边界):
       将A的前0个字符变成B的前i个字符(0 <= i <= m)只能进行插入操作，故需要的最少的操作次数为f[0][i];
       将A的前i个字符变成B的前0个字符(0 <= i <= n)只能进行删除操作，故需要的最少的操作次数为f[i][0];

    ---状态转移方程:
                    min(f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + 1), a[i] != b[j]
       f[i][j] = 
                    min(f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1]), a[i] == b[j]

⑤空间复杂度优化:

   由于在状态转移的过程中，不仅会用到f数组的上一层的结果，也会用到f数组的当前层结果，故不能进行优化。

⑥代码示例：

    scanf("%d%s",&n,a+1);
    scanf("%d%s",&m,b+1);

    //由于f数组的初始值都是0，故在状态转移的过程中求解新的状态的最小值时会出错
    //于是需要进行一步更新初始值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = INT_MAX;

    for (int i = 0; i <= n; i++)
    {
        f[i][0] = i;
    }

    for (int i = 0; i <= m; i++)
    {
        f[0][i] = i;
    }

    // f[i][j] = min(min(f[i-1][j] + 1, f[i][j-1] + 1), f[i-1][j-1] (+ 1)) ;
    // 删除：f[i-1][j] + 1 
    // 插入: f[i][j-1] + 1 
    // 替换: f[i-1][j-1] + 1 ; a[i] != b[j]
    //不操作：f[i][j] = f[i-1][j-1]; a[i] == b[j]
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {   
            //先将三种操作都做一遍，得到各自的最少操作次数
            f[i][j] = min(min(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + 1;
            //如果最后一个字符是相等的，此时可以考虑不操作，于是在将不操作的情况讨论一下
            //计算四种情况的最小值
            if(a[i] == b[j]) f[i][j] = min(f[i-1][j-1], f[i][j]);
        }

    cout << f[n][m] << endl;