#include <string>

using std::string;

/* BEGIN */

#include <cstring>
#include <algorithm>

using std::min;

#define L 1000

int dp[L + 1][L + 1];

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        dp[0][0] = 0;
        for (int i = 1; i <= s1.size(); i++) { // The boundary is very important!
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for (int j = 1; j <= s2.size(); j++) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }
        for (int i = 1; i <= s1.size(); i++) {
            for (int j = 1; j <= s2.size(); j++) {
                int c1 = s1[i - 1], c2 = s2[j - 1];
                int cost = min(dp[i - 1][j] + c1, dp[i][j - 1] + c2);
                if (c1 == c2) {
                    dp[i][j] = min(dp[i - 1][j - 1], cost);
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1] + c1 + c2, cost);
                }
            }
        }
        return dp[s1.size()][s2.size()];
    }
};

/* END */

#include <iostream>

using std::cout; using std::endl;

int main() {
    string s1 = "delete";
    string s2 = "leet";
    Solution *sol = new Solution();
    int ans = sol->minimumDeleteSum(s1, s2);
    cout << s1 << " vs " << s2 << ": " << ans << endl;

    s1 = "sea";
    s2 = "eat";
    ans = sol->minimumDeleteSum(s1, s2);
    cout << s1 << " vs " << s2 << ": " << ans << endl;

    s1 = "a";
    s2 = "at";
    ans = sol->minimumDeleteSum(s1, s2);
    cout << s1 << " vs " << s2 << ": " << ans << endl;
}