leetcode 712. Minimum ASCII Delete Sum for Two Strings 动态规划DP的典型变形题

古城微笑少年丶 2022-06-03 08:50 108阅读 0赞

Given two strings s1, s2, find 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.  
Note:

0 < s1.length, s2.length <= 1000.  
All elements of each string will have an ASCII value in \[97, 122\].

这道题给了我们两个字符串，让我们删除一些字符使得两个字符串相等，我们希望删除的字符的ASCII码最小。**这道题跟之前那道Delete Operation for Two Strings极其类似，那道题让求删除的最少的字符数，这道题换成了ASCII码值。其实很多大厂的面试就是这种改动，虽然很少出原题，但是这种小范围的改动却是很经常的，所以当背题侠是没有用的，必须要完全掌握了解题思想，并能举一反三才是最重要的。**

看到这种玩字符串又是求极值的题，想都不要想直接上DP，我们建立一个二维数组dp，其中dp\[i\]\[j\]表示字符串s1的前i个字符和字符串s2的前j个字符变相等所要删除的字符的最小ASCII码累加值。那么我们可以先初始化边缘，即有一个字符串为空的话，那么另一个字符串有多少字符就要删多少字符，才能变空字符串。所以我们初始化dp\[0\]\[j\]和dp\[i\]\[0\]，计算方法就是上一个dp值加上对应位置的字符，有点像计算累加数组的方法，由于字符就是用ASCII表示的，所以我们不用转int，直接累加就可以。这里我们把dp\[i\]\[0\]的计算放入大的循环中计算，是为了少写一个for循环。好，现在我们来看递推公式，需要遍历这个二维数组的每一个位置即dp\[i\]\[j\]，当对应位置的字符相等时，s1\[i-1\] == s2\[j-1\]，(注意由于dp数组的i和j是从1开始的，所以字符串中要减1)，那么我们直接赋值为上一个状态的dp值，即dp\[i-1\]\[j-1\]，因为已经匹配上了，不用删除字符。如果s1\[i-1\] != s2\[j-1\]，那么就有两种情况，我们可以删除s\[i-1\]的字符，且加上被删除的字符的ASCII码到上一个状态的dp值中，即dp\[i-1\]\[j\] + s1\[i-1\]，或者删除s\[j-1\]的字符，且加上被删除的字符的ASCII码到上一个状态的dp值中，即dp\[i\]\[j-1\] + s2\[j-1\]。这不难理解吧，比如sea和eat，当首字符s和e失配了，那么有两种情况，要么删掉s，用ea和eat继续匹配，或者删掉e，用sea和at继续匹配，记住删掉的字符一定要累加到dp值中才行，参见代码如下：

建议和[leetcode 583. Delete Operation for Two Strings 最长公共子串 + DP动态规划][leetcode 583. Delete Operation for Two Strings _ _ DP]和[leetcode 718. Maximum Length of Repeated Subarray 最长公共子串 + 动态规划DP][leetcode 718. Maximum Length of Repeated Subarray _ _ _DP] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int minimumDeleteSum(string s1, string s2) 
        {
            int m = s1.length(), n = s2.length();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            for (int i = 1; i <= m; i++)
                dp[i][0] = dp[i - 1][0] + (int)(s1[i-1]);
            for (int i = 1; i <= n; i++)
                dp[0][i] = dp[0][i-1] + (int)(s2[i-1]);
            for (int i = 1; i <= m; i++)
            {
                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] + (int)s1[i-1], dp[i][j - 1] + (int)s2[j-1]);
                }
            }
            return dp[m][n];
        }
    };

[leetcode 583. Delete Operation for Two Strings _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78836754
[leetcode 718. Maximum Length of Repeated Subarray _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78885152