Envío 5512

Código

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<n;i++)
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define lli long long int
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
ostream& operator<<(ostream& os, const vector<int> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<endl;
    return os;
}
const lli mod=(1e9)+7;
const int N = 1e4+1;

string a,b;
int memo[1080][1080];
int dp(int i, int j){//i->idx for A j->idx for B
    if(memo[i][j]!=-1)return memo[i][j];
    if(j>=b.size())return(i>=a.size() ?  0 :  a.size()-i);
    if(i>=a.size())return (b.size() - j); //se acabaron los de A, solo se puede insertar el resto
    int &calc = memo[i][j];
    int cost = 0;
    //return cost+dp()
    //try inserting
    int k1 = 1+dp(i,j+1);
    //try removing
    int k2 = 1+dp(i+1,j);
    //try replacing
    int k3 = 1+dp(i+1,j+1);
    int ans = min(k1,k2);
    ans = min(k3,ans);
    //try using the same if possible
    if(a[i]==b[j]){
        int k4 = dp(i+1,j+1);
        ans = min(ans,k4);
    }
    return calc = ans;
}

int main(){
    fast_io;
    cin>>a>>b;
    memset(memo,-1,sizeof(memo));
    cout<<dp(0,0)<<endl;
    return 0;
}