712. 两个字符串的最小ASCII删除和

参考链接：http://www.cnblogs.com/A-Little-Nut/p/8439094.html

利用动归的思想，使用二维辅助数组 dp[i][j]，其含义代表字符串 s1 的子串 s1.sub(0,i-1) 和 s2 的子串 s2.sub(0,j-1) 需删除字符的ASCII值的最小和。
（因为字符串的对于每个字符的位置是从基数 0 开始的）

根据上述说明的 dp[i][j] 的含义，其中，s1 的子串 s1.sub(0,i-1) 可以看作是 s1.sub(0,i-2)+s1(i-1) 组合而成，s2 的子串 s2.sub(0,j-1) 可以看作是 s2.sub(0,j-2)+s2(j-1) 组合而成。(s(x) 表示字符串 s 的下标为 x 的字符)。

public static int minimumDeleteSum(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    dp[0][0] = 0;
    for (int j = 1; j < len2+1; j++) {
        dp[0][j] = dp[0][j - 1] + s2.charAt(j-1);
    }
    for (int i = 1; i < len1+1; i++) {
        dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        for (int j = 1; j < len2+1; 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];
}

对应上述算法，当 s1.charAt(i-1)!=s2.charAt(j-1) 时
因此 dp[i][j] 可以看作两种组合：

(1) s1.sub(0,i-2)+s1(i-1) 与 s2.sub(0,j-1)（通俗的说，就是在 s1 的子串s1.sub(0,i-2) 与 s2 的子串 s2.sub(0,j-1)的基础上，在子串s1.sub(0,i-2) 最右边加上字符 s1(i-1) ），其中 s1.sub(0,i-2) 与 s2.sub(0,j-1) 就对应 dp[i-1][j]（代表 s1 的子串 s1.sub(0,i-2) 与 s2 的子串 s2.sub(0,j-1) 在两个字符串相等时所需删除字符的ASCII值的最小和），且此时 s1(i-1) 需要被删除，才能维持 s1.sub(0,i-1) 与 s2.sub(0,j-1) 在原删除了字符的基础上继续相等；

(2) s1.sub(0,i-1) 与 s2.sub(0,j-2)+s2(j-1)，其中 s1.sub(0,i-1) 与 s2.sub(0,j-2) 就对应 dp[i][j-1]，此时 s2(j-1) 需要被删除。

并且需要动态的比较是删除 s1(i-1) 还是删除 s2(j-1) 带来的代价小一点。