Minimum ASCII Delete Sum for Two Strings LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long int solve(int i, int j, string &s, string &t, vector<vector<int>> &dp) {
4
    if (i < 0) {
5
      long long ans = 0;
6
      for (int k = 0; k < j + 1; k++) {
7
        int x = int(t[k]);
8
        ans += x;
9
      }
10
      return ans;
11
    }
12
    if (j < 0) {
13
      long long ans = 0;
14
      for (int k = 0; k < i + 1; k++) {
15
        int x = int(s[k]);
16
        ans += x;
17
      }
18
      return ans;
19
    }
20
    if (dp[i][j] != -1) return dp[i][j];
21
    if (s[i] == t[j])
22
      return dp[i][j] = solve(i - 1, j - 1, s, t, dp);
23
    else {
24
      long long x = int(s[i]) + solve(i - 1, j, s, t, dp);
25
      long long y = int(t[j]) + solve(i, j - 1, s, t, dp);
26
      return dp[i][j] = min(x, y);
27
    }
28
  }
29
  long long int minimumDeleteSum(string s1, string s2) {
30
    int n = s1.size();
31
    int m = s2.size();
32
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
33
    return solve(n - 1, m - 1, s1, s2, dp);
34
  }
35
};