CSES – Edit Distance

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 5005;
int dp[maxn][maxn];
string s,t;
//
signed main(){
    fastio;
    cin>>s>>t;
    s = '#' + s, t = '#' + t;
    for(int i=1;i<=s.size();i++) dp[i][0] = i;
    for(int i=1;i<=t.size();i++) dp[0][i] = i;
    for(int i=1;i<=s.size();i++){
        for(int j=1;j<=t.size();j++){
            if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]}) + 1;
        }
    }
    cout<<dp[s.size()][t.size()]<<"\n";
    return 0;
}