代码随想录day56【动态规划】【子序列问题】 两个字符串的删除操作 编辑距离

两个字符串的删除操作

力扣题目链接
法一

1. dp数组含义：
   dp[i][j]:以i-1,j-1结尾的最少删除个数
2. 递推公式：
   dp[i]==dp[j-1],dp[i][j]=dp[i-1][j-1]
   dp[i]!=dp[j-1],dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2) 其中，,dp[i][j-1]+1包含了dp[i-1][j-1]+2，故可简化为min(dp[i-1][j]+1,dp[i][j-1]+1)
3. 初始化：
   dp[i][0]=i,dp[0][j]=j, 相当于其中一个为空串，则操作次数为i/j
4. 遍历顺序
   顺序

var minDistance = function(word1, word2) {
    let dp=new Array(word1.length+1).fill(0).map(()=> new Array(word2.length+1).fill(0))
    for(let i=0;i<=word1.length;i++){
        dp[i][0]=i
    }
    for(let j=0;j<=word2.length;j++){
        dp[0][j]=j
    }
    for(let i=1;i<=word1.length;i++){
        for(let j=1;j<=word2.length;j++){
            if(word1[i-1]===word2[j-1]){
              dp[i][j]=dp[i-1][j-1]
            }else{
                dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1) 
            }
        }
    }
    return dp[word1.length][word2.length]
};

法二
利用最长公共子序列，
最后求得的结果=word1.length+word2.length-最长公共子序列*2

编辑距离

力扣题目链接

1. dp数组含义：
   dp[i][j]:以i-1,j-1结尾的最少删除个数
2. 递推公式：
   dp[i]==dp[j-1],dp[i][j]=dp[i-1][j-1]
   dp[i]!=dp[j-1],dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
3. 初始化：
   dp[i][0]=i,dp[0][j]=j，相当于其中一个为空串，则操作次数为i/j
4. 遍历顺序
   顺序

var minDistance = function(word1, word2) {
    let dp=new Array(word1.length+1).fill(0).map(()=> new Array(word2.length+1).fill(0))
    for(let i=0;i<=word1.length;i++){
        dp[i][0]=i
    }
    for(let j=0;j<=word2.length;j++){
        dp[0][j]=j
    }
    for(let i=1;i<=word1.length;i++){
        for(let j=1;j<=word2.length;j++){
            if(word1[i-1]===word2[j-1]){
              dp[i][j]=dp[i-1][j-1]
            }else{
                dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1) 
            }
        }
    }
    return dp[word1.length][word2.length]
};