简单的动态规划

#include<bits/stdc++.h>
using namespace std;
string comp_distance(string &str1,string &str2){
    str1.insert(0,1,'#');
    str2.insert(0,1,'#');
    int len1=str1.size();
    int len2=str2.size();
    vector<vector<int> > dp(len1,vector<int>(len2,0));
    for(int i=0;i<len1;i++){
        dp[i][0]=i;
    }
    for(int i=0;i<len2;i++){
        dp[0][i]=i;
    }
    for(int i=1;i<len1;i++){
        for(int j=1;j<len2;j++){
            if(str1[i]==str2[j])
                dp[i][j]=dp[i-1][j-1];
            else{
                dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
            }
        }
    }
    return "1/"+to_string(dp[len1-1][len2-1]+1);
}
int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        cout<<comp_distance(str1,str2)<<endl;
    }
    return 0;
}