Saleh127

UVA 1207 / DP - Edit dis

Oct 22nd, 2021
1,110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-23-02.46.09
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10.  
  11. ll dp[1002][1002];
  12. string a,b;
  13. ll n,m;
  14.  
  15. ll solve(ll i,ll j)
  16. {
  17.      if(i==n) return m-j;
  18.  
  19.      if(j==m) return n-i;
  20.  
  21.      if(dp[i][j]!=-1) return dp[i][j];
  22.  
  23.      ll ans=1e6;
  24.  
  25.      if(a[i]==b[j])
  26.      {
  27.           ans=min(ans,solve(i+1,j+1));
  28.      }
  29.      else
  30.      {
  31.           ans=min(ans,1+solve(i+1,j+1)); ///change i or j th char
  32.           ans=min(ans,1+solve(i+1,j));  ///dlt i th char
  33.           ans=min(ans,1+solve(i,j+1));  ///insrt j th char
  34.      }
  35.  
  36.      return dp[i][j]=ans;
  37. }
  38.  
  39. int main()
  40. {
  41.    ios_base::sync_with_stdio(0);
  42.    cin.tie(0);cout.tie(0);
  43.  
  44.  
  45.    while(cin>>n>>a>>m>>b)
  46.    {
  47.         memset(dp,-1,sizeof dp);
  48.  
  49.         cout<<solve(0,0)<<endl;
  50.    }
  51.  
  52.  
  53.    get_lost_idiot;
  54. }
  55.  
RAW Paste Data