pls give correct base case for the standard dp problem edit distance I m struggling little bit as i m beginner
I m trying this problem recursively
my solution:
#include"bits/stdc++.h"
using namespace std;
#define ll long long int
vector<vector >dp;
ll ans;
ll recur(ll i,ll j,string s1,string s2)
{
if(i>=s1.size())
return (s2.size()-i);
if(j>=s2.size())
return (s1.size()-j);
if(dp[i][j]!=-1)return dp[i][j];
else if(s1[i-1]==s2[j-1])
ans=recur(i+1,j+1,s1,s2);
else
{
ans=1+min(recur(i+1,j+1,s1,s2),min(recur(i,j+1,s1,s2),recur(i+1,j,s1,s2)));
}
return dp[i][j]=ans;
}
ll solve(string s1,string s2)
{
ll ans1=recur(1,1,s1,s2);
return ans1;
}
int main()
{
string s1,s2;
cin>>s1>>s2;
ll s1_l=s1.size();
ll s2_l=s2.size();
dp.resize(s1_l+1,vector(s2_l+1,-1));
ll ans2=solve(s1,s2);
cout<<ans2<<endl;
}