leetcode

0 class Solution {

1 int dp[1001][1001];

2 int rec(const string &s1, const string &s2, int l1, int l2) {

3 if (l1 >= s1.size() && l2 >= s2.size()) return 0;

4 if (dp[l1][l2] != -1) return dp[l1][l2];

5

6 int res = INT_MAX;

7 if (s1[l1] == s2[l2]) res = min(res, rec(s1, s2, l1 + 1, l2 + 1));

8 res = min(res, s1[l1] + rec(s1, s2, l1 + 1, l2));

9 res = min(res, s2[l2] + rec(s1, s2, l1, l2 + 1));

10

11 return dp[l1][l2] = res;

12 }

13

14 public:

15 Solution() { memset(dp, 0xFF, sizeof(dp)); }

16 int minimumDeleteSum(const string &s1, const string &s2) {

17 for (int i = s1.size() - 1, sum = 0; i >= 0; i--)

18 dp[i][s2.size()] = sum += s1[i];

19 for (int i = s2.size() - 1, sum = 0; i >= 0; i--)

20 dp[s1.size()][i] = sum += s2[i];

21

22 return rec(s1, s2, 0, 0);

23 }

24 };