一起刷LeetCode——两个字符串的最小ASCII删除和（动态规划）

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

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

分析

• 要想使两个字符串相等，首先要查找两个字符串是否有相等字母，去掉不同的字母的ASCII码就是最小和，在去掉字母的时候有几种不同的情况，最小ASCII删除和就在这几种状态中，可以尝试通过动态规划来求解
• 状态定义：dp[i][j]表示第一个字符串s1下标从0-i的子串和s2下标从0到j的子串相等时删除的最小的ASCII和
• 状态转移：
  • 当其中有个字符串为空时，答案就是另一个字符串ASCII码的和
    • dp[i][j] = sum(s2)(i=0) dp[i][j]=sum(s1)(j=0)
  • 当s1的第i个字母与s2的第j个字母相同时
    • dp[i-1]=dp[j-1] (s1[i]===s2[j])
  • 当最后一个字符不同时，有3种情况
    • 删除s1的最后一个字符m，dp[i][j]=ASCII(m) + dp[i-1][j]
    • 删除s2的最后一个字符n，dp[i][j]=ASCII(n) + dp[i][j-1]
    • 删除s1的最后一个字符m和s2的最后一个字符n，dp[i][j]=ASCII(m) + ASCII(n) + dp[i-1][j-1]
    • 从这三个中取最小的那个数作为dp[i][j]的值
• 题目答案就是dp[s1.length][s2.length]

代码

var minimumDeleteSum = function(s1, s2) {
    let m = s1.length();
    let n = s2.length();
    let dp = new Array(m + 1).map(e => new Array(n +1)
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(i==0 || j==0){
                int a = 0;
                for(int z=1;z<=Math.max(j,i);z++){
                    a += (i==0?s2.charAt(z-1):s1.charAt(z-1));
                }
                dp[i][j] = a;
            }
            else if(s1.charAt(i-1)==s2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1];
            }
            else{
                dp[i][j] = Math.min(s1.charAt(i-1)+dp[i-1][j],s2.charAt(j-1)+dp[i][j-1]);
                dp[i][j] = Math.min(dp[i][j],s1.charAt(i-1)+s2.charAt(j-1)+dp[i-1][j-1]);
            }
        }
    }
    return dp[m][n];
};
        

总结

• 根据题意分析，分析出来很多情况，根据不同的情况得到不同的公式，把一个问题分成许多个小问题，是动态规划的体现。因此本题使用动态规划。不是看完之后确定这个题要用什么方法去解决，而是有了很多方法的积累通过分析，用什么方法解决更好。
• 今天也是有收获的一天