leetcode712. 两个字符串的最小ASCII删除和（最短非公共子序列）

传送门

题目：给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
输入: s1 = “sea”, s2 = “eat”
输出: 231
解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。
在 “eat” 中删除 “t” 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和

和1143题求的是互补的序列

动态过程中有三种状态（这里没有在字符串前加冗余字符，所以dp[i]比较的是字符s[i-1]）

1.s1[i-1] == s2[j-1]，新增的两个字符相等的情况下没有必要删除之前的结果，因此dp[i][j] = dp[i-1][j-1]

2.s1[i-1] != s2[j-1]，取三者的最小值
（1）保留s2串，删除s1串的字符，dp[i][j] = dp[i-1][j] + s1.charAt(i-1)
（2）保留s1串，删除s2串的字符，dp[i][j] = dp[i][j-1] + s1.charAt(j-1)
（3）删除s1、s2串的字符，dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1) + s2.charAt(j-1)

但是第三中情况会被包含在1或者2里，可以不写到dp里

1.加冗余字符的写法（dp[i][j]就对应的s1[i] s2[j]）

 	public int minimumDeleteSum(String s1, String s2) {
        s1 = 'a' + s1; // 两个字符串前面加上冗余字符，dp[i][j]就比较的是字符s1[i]，s2[j]
        s2 = 'a' + s2;
        int[][] dp = new int[s1.length()][s2.length()];
         
         // 注意：要初始化dp[0][j]和dp[i][0],这个初始化就算没有加冗余也要做的
         // 因为下面方程用到了dp[0][j] 和dp[i][0]
        for (int i = 1; i < s1.length(); ++i) {  
            dp[i][0] = dp[i - 1][0] + s1.charAt(i);// 不是累加
        }
        for (int j = 1; j < s2.length(); ++j) {
           dp[0][j] = dp[0][j - 1] + s2.charAt(j); // 不是累加
        }
        
        for (int i = 1; i < s1.length(); ++i) {
            for (int j = 1; j < s2.length(); ++j) {
                if (s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i - 1][j] + s1.charAt(i),//删除i
                        dp[i][j - 1] + s2.charAt(j),// 删除j
                        dp[i - 1][j - 1] + s1.charAt(i) + s2.charAt(j));//删除i和j, 可以省略
            }
        }
        return dp[s1.length() - 1][s2.length() - 1];
    }
    // 取a b c 最小值
    int min(int a, int b, int c) {
        int tmp = a < b ? a : b;
        return tmp < c ? tmp : c;
	}

2. 不加冗余字符，dp[i][j]代表的是字符串i-1，j-1的位置 1143里类似的方法

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int i = 1; i <= len1; ++i) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        
        for (int j = 1; j <= len2; ++j) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), 
						dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
            
        }
        return dp[len1][len2];
    }
}