Advertisement
Josif_tepe

Untitled

Oct 3rd, 2022
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6. string A, B;
  7. int dp[1005][1005];
  8. int dp_1[1005][1005];
  9. int rec(int i, int j) {
  10.     if(i == -1 and j == -1) {
  11.         return 0;
  12.     }
  13.     if(i == -1) {
  14.         return j + 1;
  15.     }
  16.     if(j == -1) {
  17.         return i + 1;
  18.     }
  19.     if(dp[i][j] != -1) {
  20.         return dp[i][j];
  21.     }
  22.     int result = 2e9;
  23.     if(A[i] == B[j]) {
  24.         result = min(result, rec(i - 1, j - 1) + 1);
  25.     }
  26.     result = min(result, rec(i - 1, j) + 1);
  27.     result = min(result, rec(i, j - 1) + 1);
  28.     return dp[i][j] = result;
  29. }
  30.  
  31. int combinations(int i, int j) {
  32. if(i==-1 or j==-1){
  33. return 1;
  34. }
  35. if(dp_1[i][j]!=-1){
  36.     return dp_1[i][j];
  37. }
  38. int result=0;
  39. if(A[i]==B[j]){
  40. result+=combinations(i-1, j-1);
  41. }
  42. else {
  43. if(rec(i-1, j)==rec(i, j-1)){
  44.     result+=combinations(i-1, j);
  45.     result+=combinations(i, j-1);
  46. }
  47. else if(rec(i-1, j)>rec(i, j-1)){
  48. result+=combinations(i, j-1);
  49. }
  50. else if(rec(i-1, j)<rec(i, j-1)){
  51.     result+=combinations(i-1, j);
  52. }
  53. }
  54.     result  %= 750083;
  55. return dp_1[i][j]=result;
  56. }
  57. int main()
  58. {
  59.     cin >> A >> B;
  60.  
  61.     memset(dp, -1, sizeof dp);
  62.     memset(dp_1, -1, sizeof dp_1);
  63.     rec((int) A.size() - 1, (int) B.size() - 1);
  64.     cout <<combinations((int) A.size() - 1, (int) B.size() - 1) << endl;;
  65.  
  66.     return 0;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement