Minimum ASCII Delete Sum for Two Strings

dp[i][j] represents the minimum delete sum to make the first i-1 characters of string A and the first j-1 characters of string B equal. For each character at position i-1, we decide whether to delete the corresponding character at j-1. If the two characters match, we don’t delete either and set dp[i][j] = dp[i-1][j-1]. Otherwise we must delete one of them and take the minimum cost option for dp[i][j].

int minimumDeleteSum(string& s1, string& s2) {
    int m = s1.size();
    int n = s2.size();
    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
    
    for(int i = 0; i < n; ++i)
        dp[0][i+1] = s2[i] + dp[0][i];

    for(int i = 1; i <= m; ++i) {
        dp[i][0] = s1[i-1] + dp[i-1][0];
        for(int j = 1; j <= n; ++j) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
        }
    }
    return dp[m][n];
}

#DP

Maximum Sum of Two Non-Overlapping Subarrays Minimum Cost for Tickets: A Dynamic Programming Approach