dp动规编辑距离思想

解题思路: 

三种操作分别是：

1. 插入 

2. 删除

3. 替换

   
   

需要清楚的点： 

1. 两字符串A和B，给A插入相当于给B删除，反之亦然（例如cat和cate）

2. 替换A相当于替换B（例如cat和fat）

故本质操作就三种 ： ① A插 ② B插 ③ 替换

dp[i][j]表示从 A 的 前 i 个 字 符 转换到 B 的 前 j 个 字 符 所需的最短步数

（例如A是qwert B是aserty 那么最终输出结果就是dp[5][6]）

 dp[i-1][j-1]到dp[i][j]需要进行替换操作

若A的第 i 位(其实就是当前操作位）等于 B的第 j 位（其实就是当前操作位），那么就不需要替换，因此dp[i][j] = dp[i-1][j-1] ，否则dp[i][j] = dp[i-1][j-1]+1

 dp[i-1][j]到d[i][j]需要进行删除操作

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

 dp[i][j-1]到d[i][j]需要进行添加操作

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

★当A与B末位相同时：

dp[i][j] = min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1]) 

★当A与B末位不相同时：

dp[i][j] =1+min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])

***那么，我们要怎么从dp[0][0] 到 dp[i][j]呢？

很简单，每一步做出判断，替换、删除、添加哪个短就选哪个！

这里需要注意，①dp[a][b]代表着前面所有步数的最短选择！②由于不知道AB长度，因此A插和B插不可以混为一谈！

注意事项: 

边界情况，A或B为空，直接输出不为空的数组长度即可

参考代码:

#include

using namespace std;

int main(){

    //注意！！数组是从0开始索引的，所以第i位就是i-1的索引，以此类推！！

    string a,b;

    getline(cin,a);

    getline(cin,b);

    int len1 = a.length();

    int len2 = b.length(); //接受输入记录长度

    int dp[len1][len2]; //定义dp数组

    for (int i = 0; i < len1; i++) {dp[i][0] = i;}

    for (int j = 0; j < len2; j++) {dp[0][j] = j;}  //边界情况,同时也是初始化

    for (int i = 1; i < len1; i++)

    {

        for (int j = 1; j < len2; j++) //ij从1开始，因为已经初始化过了,从0开始会溢出

        {

            if(a[i-1] == b[j-1]) //A的第i位与B的第j位相同的情况

            dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]);

            else

            dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]+1);

        }

    }

    cout<<dp[len1-1][len2-1]<<endl;

    return 0;

}