So, I just solved this classic DP Problem called “Edit Distance”.
And how can i make this code run faster?
I got AC in 0.4s, is that possible to make DP Top-Down method runs below 0.1s?
Code:
#include <bits/stdc++.h>
using namespace std;
string a,b;
int dp[3005][3005];
int f(int ai, int bi){
if (ai < 0) return bi;
if (bi < 0) return ai;
if (dp[ai][bi] != -1) return dp[ai][bi];
if (a[ai]==b[bi])
return dp[ai][bi] = f(ai-1,bi-1);
return dp[ai][bi] = 1 + min(min( f(ai,bi-1), f(ai-1,bi) ), f(ai-1,bi-1) );
}
int main(){
int t;
cin >> t;
while (t--){
cin >> a >> b;
memset(dp,-1,sizeof dp);
cout << f(a.size()-1,b.size()-1)+1 << endl;
}
}