0712.cpp (846B)
1 class Solution { 2 int dp[1001][1001]; 3 int rec(const string &s1, const string &s2, int l1, int l2) { 4 if (l1 >= s1.size() && l2 >= s2.size()) return 0; 5 if (dp[l1][l2] != -1) return dp[l1][l2]; 6 7 int res = INT_MAX; 8 if (s1[l1] == s2[l2]) res = min(res, rec(s1, s2, l1 + 1, l2 + 1)); 9 res = min(res, s1[l1] + rec(s1, s2, l1 + 1, l2)); 10 res = min(res, s2[l2] + rec(s1, s2, l1, l2 + 1)); 11 12 return dp[l1][l2] = res; 13 } 14 15 public: 16 Solution() { memset(dp, 0xFF, sizeof(dp)); } 17 int minimumDeleteSum(const string &s1, const string &s2) { 18 for (int i = s1.size() - 1, sum = 0; i >= 0; i--) 19 dp[i][s2.size()] = sum += s1[i]; 20 for (int i = s2.size() - 1, sum = 0; i >= 0; i--) 21 dp[s1.size()][i] = sum += s2[i]; 22 23 return rec(s1, s2, 0, 0); 24 } 25 };