# Untitled

Oct 3rd, 2022
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.