Advertisement
Josif_tepe

Untitled

Dec 30th, 2022
917
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. string s1, s2;
  6. int dp[5005][5005];
  7. int rec(int i, int j) {
  8.     if(i == -1) {
  9.         return j + 1;
  10.     }
  11.     if(j == -1) {
  12.         return i + 1;
  13.     }
  14.     if(dp[i][j] != -1) {
  15.         return dp[i][j];
  16.     }
  17.     int result = 2e9;
  18.     if(s1[i] == s2[j]) {
  19.         result = min(result, rec(i - 1, j - 1));
  20.     }
  21.     result = min(result, rec(i - 1, j) + 1);
  22.     result = min(result, rec(i, j - 1) + 1);
  23.     result = min(result, rec(i - 1, j - 1) + 1);
  24.     return dp[i][j] = result;
  25. }
  26. int main() {
  27.     cin >> s1 >> s2;
  28.     memset(dp, -1, sizeof dp);
  29.     cout << rec(s1.size() - 1, s2.size() - 1) << endl;
  30.     return 0;
  31. }
  32.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement