712. Minimum ASCII Delete Sum for Two Strings(M)

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Constraints:

• 1 <= s1.length, s2.length <= 1000

• s1 and s2 consist of lowercase English letters.

Solution:

这道题，和上一道题非常类似，这回不问我们删除的字符个数了，问我们删除的字符的 ASCII 码加起来是多少。

那就不能直接复用计算最长公共子序列的函数了，但是可以依照之前的思路，稍微修改 base case 和状态转移部分即可直接写出解法代码：

// 备忘录
int memo[][];
/* 主函数 */    
int minimumDeleteSum(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 备忘录值为 -1 代表未曾计算
    memo = new int[m][n];
    for (int[] row : memo) 
        Arrays.fill(row, -1);

    return dp(s1, 0, s2, 0);
}

// 定义：将 s1[i..] 和 s2[j..] 删除成相同字符串，
// 最小的 ASCII 码之和为 dp(s1, i, s2, j)。
int dp(String s1, int i, String s2, int j) {
    int res = 0;
    // base case
    if (i == s1.length()) {
        // 如果 s1 到头了，那么 s2 剩下的都得删除
        for (; j < s2.length(); j++)
            res += s2.charAt(j);
        return res;
    }
    if (j == s2.length()) {
        // 如果 s2 到头了，那么 s1 剩下的都得删除
        for (; i < s1.length(); i++)
            res += s1.charAt(i);
        return res;
    }

    if (memo[i][j] != -1) {
        return memo[i][j];
    }

    if (s1.charAt(i) == s2.charAt(j)) {
        // s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
        memo[i][j] = dp(s1, i + 1, s2, j + 1);
    } else {
        // s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
        memo[i][j] = Math.min(
            s1.charAt(i) + dp(s1, i + 1, s2, j),
            s2.charAt(j) + dp(s1, i, s2, j + 1)
        );
    }
    return memo[i][j];
}


Another Version:
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        String lcs = getLongestCommonSeq(s1, s2);
        int result1 = 0, result2 = 0;;
        int left = 0; int right = 0;
        while(left< s1.length() && right < lcs.length())
        {
            if(s1.charAt(left) == lcs.charAt(right))
            {
                right++;
            }
            else
            {
                result1 += (int)s1.charAt(left);
            }
            left++;
        }
        
        while(left < s1.length())
        {
            result1 += s1.charAt(left);
            left++;
        }
        while(right < lcs.length())
        {
            result1 += lcs.charAt(right);
            right++;
        }
        
        
        
        left = 0; right = 0;
        while(left< s2.length() && right < lcs.length())
        {
            if(s2.charAt(left) == lcs.charAt(right))
            {
                left++;
                right++;
            }
            else
            {
                result2 += (int)s2.charAt(left);
                left++;
            }
        }
        while(left < s2.length())
        {
            result2 += s2.charAt(left);
            left++;
        }
        while(right < lcs.length())
        {
            result2 += lcs.charAt(right);
            right++;
        }
        return result1 + result2;
        
    }
    
    public String getLongestCommonSeq(String s1, String s2)
    {
        int l1 = s1.length();
        int l2 = s2.length();
        String[][] dp = new String[l1+1][l2+1];
        for(int i = 0; i<=l1; i++)
        {
            dp[i][0] = "";
        }
        for(int i = 0; i<= l2; i++)
        {
            dp[0][i] = "";
        }
        for(int i = 1; i<=l1; i++)
        {
            for(int j = 1; j<=l2; j++)
            {
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    dp[i][j] = new StringBuilder(dp[i-1][j-1]).append(s1.charAt(i-1)).toString();
                }
                else
                {
                    dp[i][j] = getMaxString(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[l1][l2];
    }
    
    public String getMaxString(String s1, String s2)
    {
        if(s1.length() == s2.length())
        {
            int result1 = 0; int result2 = 0;
            for(int i = 0; i< s1.length(); i++)
            {
                result1 += (int) s1.charAt(i);
                result2 += (int) s2.charAt(i);
            }
            if(result1 > result2) return s1;
            else return s2;
        }
        return s1.length() > s2.length() ? s1 : s2;
    }
}

base case 有一定区别，计算lcs长度时，如果一个字符串为空，那么lcs长度必然是 0；但是这道题如果一个字符串为空，另一个字符串必然要被全部删除，所以需要计算另一个字符串所有字符的 ASCII 码之和。

关于状态转移，当s1[i]和s2[j]相同时不需要删除，不同时需要删除，所以可以利用dp函数计算两种情况，得出最优的结果。其他的大同小异，就不具体展开了。

至此，三道子序列问题就解决完了，关键在于将问题细化到字符，根据每两个字符是否相同来判断他们是否在结果子序列中，从而避免了对所有子序列进行穷举