Advertisement
Josif_tepe

Untitled

Nov 15th, 2021
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2. #include<ctime>
  3. #include<map>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7. string a, b;
  8. int dp[1005][1005];
  9. int rec(int pos_a, int pos_b) {
  10.     if(pos_a == -1 or pos_b == -1) {
  11.         return 0;
  12.     }
  13.     if(dp[pos_a][pos_b] != -1) {
  14.         return dp[pos_a][pos_b];
  15.     }
  16.     int result = 0;
  17.     if(a[pos_a] == b[pos_b]) {
  18.         result = max(result, rec(pos_a - 1, pos_b - 1) + 1);
  19.     }
  20.     result = max(result, rec(pos_a - 1, pos_b));
  21.     result = max(result, rec(pos_a, pos_b - 1));
  22.     dp[pos_a][pos_b] = result;
  23.     return result;
  24. }
  25. int main()
  26. {
  27.     cin >> a >> b;
  28.     for(int i = 0; i < a.size(); i++) {
  29.         for(int j = 0; j < b.size(); j++) {
  30.             dp[i][j] = -1;
  31.         }
  32.     }
  33.     cout << rec(a.size() - 1, b.size() - 1) << endl;
  34.  
  35.     return 0;
  36. }
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement