和两个字符串的最长公共子序列差不多的类型。

两个字符串，一个字符串通过增加，修改，删除一个字符能够和另一个字符串。

方法一

常规分析法：
两个字符串在比较某个字符的时候可以（stra[i]，strb[j]）：

1. 相等，直接推进比较
   compare(stra[i+1],strb[j+1])
   修改+0
2. 两个字符串之一通过添加字符，达到相等，然后推进比较
   compare(stra[i+1],strb[j])，或者另一个增加1
   修改+1
3. 两个字符串通过修改字符串达到相等，然后推进
   compare(stra[i+1],strb[j+1])
   修改+1
4. 两个字符串之一通过删除字符，不能相等，直接推进比较
   compare(stra[i+1],strb[j+1])
   修改+1

我们需要一个memo来记录当前长度时，修改的次数。

这种方法，其实也是一种动态规划了。

memo[i][j]存放的是从stra的i到尾部，与从strb的i到strb的尾部这两个字符串，如果要匹配相等需要的距离，也就是改变。
为什么要这样递归，也就是为什么要这样存放：
这种方法是从后向前计算的每一位的。两个字符串长m,n，那么memo[m-1][n-1]，如果相等就是0，否则就是1（删除需要两步操作，修改只需要一步）。
然后最后一位匹配了，那么memo[m-2][n-2], memo[m-2][n-1],memo[m-1][n-2]，也就在这个基础上确定了。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int min(int a,int b,int c)
{
    if(a<b)
    {
        b=a;
    }
    if(b>c)
    {
        b=c;
    }
    return b;
}
            //  1234567
// string stra("qwert12");
// string strb("1qwert");

int comparestr1_ass(vector<vector<int>> &memo,string &stra,size_t starta,string &strb,size_t startb)
{

    cout<<"compare: "<<starta<<" "<<startb<<endl;
    
    int a=INT32_MAX;
    int c=INT32_MAX;
    int b=INT32_MAX;
    
 

    if(starta >= stra.size())
    {
        cout<<"___stra end"<<endl;
        if(startb >= strb.size())
        {
            return 0;
        } 
        memo[starta][startb]=strb.size()-startb;
        return memo[starta][startb];
    }
    if(startb >= strb.size())
    {
        cout<<"___strb end"<<endl;
        
        if(starta >= stra.size())
        {
            return 0;
        } 
        memo[starta][startb]=stra.size()-starta;
        return memo[starta][startb];
    }

    //相等的情况
    if(stra[starta] == strb[startb])
    {
        cout<<"equal: "<<starta<<" "<<startb<<endl;
        if(memo[starta+1][startb+1] != 0)
        {
            memo[starta][startb]=memo[starta+1][startb+1];
            return memo[starta+1][startb+1];
        }else{
            memo[starta][startb]=comparestr1_ass(memo,stra,starta+1,strb,startb+1);
            return memo[starta+1][startb+1];
        }
    }

    //处理不相等的情况
    
    if(starta<stra.size() && startb<strb.size())
    {
    cout<<"__unequal xiugai: "<<starta<<" "<<startb<<endl;
        if(memo[starta+1][startb+1] != 0)
        {
            a=memo[starta+1][startb+1];
        }else{
            a=comparestr1_ass(memo,stra,starta+1,strb,startb+1);
        }
    }
   
    
    if(starta<stra.size())
    {
    cout<<"__unequal zengjia: "<<starta<<" "<<startb<<endl;
    
        if(memo[starta+1][startb] != 0)
        {
            b=memo[starta+1][startb];
        }else{
            b=comparestr1_ass(memo,stra,starta+1,strb,startb);
        }
    }
 

    
    if(startb<strb.size())
    {

        cout<<"__unequal shanchu: "<<starta<<" "<<startb<<endl;
    
        if(memo[starta][startb+1] != 0)
        {
            c=memo[starta][startb+1];
        }else{
        
            c=comparestr1_ass(memo,stra,starta,strb,startb+1);
        }
    }
 
    
    int tmp;
    tmp = min(a,b,c);
    memo[starta][startb]=tmp+1;
    cout<<"xiugai: "<<a<<" qita: "<<b<<" "<<c<<endl;
    cout<<endl<<"end of: "<<starta<<" "<<startb<<" value: "<<tmp+1<<endl;
    

    
    for(auto j:memo)
    {
        cout<<endl;
        for(auto i:j)
        {
            cout<<i<<"  ";
        }
    }
    cout<<endl;
    cout<<endl;
    // int tmp1;
    // cin>>tmp1;

    return tmp+1;
}

int comparestr1(string stra,string strb)
{
    vector<vector<int>> memo(stra.size()+2,vector<int>(strb.size()+2,0));
    // for(int i=0;i<=stra.size();i++)
    // {
    //     memo[i][0]=i;
    // }
    // for(int i=0;i<=strb.size();i++)
    // {
    //     memo[0][i]=i;
    // }

    comparestr1_ass(memo,stra,0,strb,0);
    
    for(auto j:memo)
    {
        cout<<endl;
        for(auto i:j)
        {
            cout<<i<<"  ";
        }
    }
    cout<<endl;
    cout<<endl;
    return 1;    
}

int main()
{           //   01234567
    string stra("qwert12");
    string strb("1qwert");
    comparestr1(stra,strb);
}

这种方法，额，需要判断的东西太多。
而且代码太狗屎。

方法二