# 0712. Minimum ASCII Delete Sum for Two Strings
###### tags: `Leetcode` `Medium` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
## 思路
先用找lcs的方法找到maximum ascii common sequence
然后做减法
## Code

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        StringBuilder str1 = new StringBuilder(s1);
        StringBuilder str2 = new StringBuilder(s2);
        str1.insert(0, '#');
        str2.insert(0, '#');
        
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(str1.charAt(i)==str2.charAt(j)){
                    dp[i][j] = dp[i-1][j-1]+str1.charAt(i);
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        int sum = 0;
        for(int i=0; i<m; i++) sum += s1.charAt(i);
        for(int i=0; i<n; i++) sum += s2.charAt(i);
        return sum-2*dp[m][n];
    }
}