最小代价，毋庸置疑动态规划
和之前的最小次数比，区别点在插入，删除，替换这几个代价是不同的，所以就需要区分出来那种可以实现当前的效果，然后找最小
我们先不考虑状态压缩来进行分析

dp[i][j] 标示 str1[0,i] 变为 str2[0,j] 的最小代价
则 
dp[i][j] = dp[i-1][j-1]  {str1[i] == str2[i]}
dp[i][j] = min(
   //替换 ： 删除+ 插入
   dp[i-1][j-1]+ dc +ic,
   //替换 （两个都不要）
   dp[i-1][j-1]+rc,
   //删除 ?
   dp[i - 1][j] + dc,
   //插入 ?
   dp[i][j - 1] + ic
)  {str1[i] != str2[i]}

base case

dp[i][0] = i*dc
dp[0][j] = i+ic

比较容易迷惑的地方

dp[i - 1][j] + dc *
*为什么 i-1 的时候要加上删除的代价，而不是插入？

含义：
str1[0:i]先编辑成str1[0:i-1]，即先删除字符str1[i]，然后由str1[0:i-1]编辑成str2[0:j]
例如
str1: abcdc
str2: abcc
i = 4
j = 4 的时候
可以考虑将 i位置移除（假设从0开始）

dp[i][j - 1] + ic
为什么 j-1 的时候要机上的是插入的代价而不是删除？

含义：
str1[0:i]可以先编辑成str2[0:j-1],然后向str2[0:j-1]插入字符str2[j],编辑成str2[0:j]，
dp[i][j-1]表示str1[0:i-1]编辑成str2[0:j-2]的最小代价，那么dp[i][[j]可能等于dp[i][j-1] + ic;
可以将上面例子反过来看即可

先将空间复杂度 O(N*M) 写出来
我们再考虑如何压缩，尝试等量替换即可

package main 
import (
    "fmt"
    //"os"
    //"bufio"
    //"strconv"
)
func main(){
    var str1,str2 string 
    var ic,dc,rc int
    fmt.Scanf("%s",&str1)
    fmt.Scanf("%s",&str2)
    fmt.Scanln(&ic,&dc,&rc)
    //helper(str1,str2,ic,dc,rc)
    helper2(str1,str2,ic,dc,rc)
    return 
}
//我们先尝试不压缩

func helper(str1,str2 string ,ic,dc,rc int){
    dp := make([][]int,len(str1)+1)
    //需要移除个
    for i:=0;i<=len(str1);i++{
        dp[i] = make([]int,len(str2)+1)
        dp[i][0] = i*dc
    }
    //需要插入j个
    for j:=0;j<=len(str2);j++{
        dp[0][j] = j* ic
    }

    for i:=1;i<=len(str1);i++{
        for j:=1;j<=len(str2);j++{
            if str1[i-1] == str2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = min(dp[i-1][j-1] + rc,dp[i-1][j-1] +dc +ic)
            }
            // dp[i-1][j] +dc 标示 删除 操作？ 如果 两个不相等 删除一个 i 就变成了 i-1,j
            // dp[i][j-1] +ic 标示 插入 操作 ？ 如果两个不相等 插入一个 i,j-1 基础插入一个相同数据即可
            dp[i][j] = min(dp[i][j],min(dp[i-1][j] +dc,dp[i][j-1] +ic ))
        }
    }
    fmt.Println(dp[len(str1)][len(str2)])
    return 

}
//我们现在考虑一下状态压缩
func helper2(str1,str2 string ,ic,dc,rc int){
    dp := make([]int,len(str2)+1)
    //需要插入j个
    for j:=0;j<=len(str2);j++{
        dp[j] = j* ic
    }
    for i:=1;i<=len(str1);i++{
        pre := dp[0]
        //更新dp[0] i *dc 标示 j 为0 的情况
        dp[0] = i * dc 
        for j:=1;j<=len(str2);j++{
            // tmp 一定是将要用到的 j-1 ，本次的i-i，j
            tmp := dp[j] //tmp在循环内就是 dp[i-1][j] 因为当前的j 还是为更新状态，就是i-1位置的
            if str1[i-1] == str2[j-1] {
                dp[j] = pre
            }else{
                dp[j] = min(pre + rc,pre +dc +ic)
            }
            // dp[i-1][j] +dc 标示 删除 操作？ 如果 两个不相等 删除一个 i 就变成了 i-1,j
            // dp[i][j-1] +ic 标示 插入 操作 ？ 如果两个不相等 插入一个 i,j-1 基础插入一个相同数据即可
            dp[j] = min(dp[j],min(tmp +dc,dp[j-1] +ic ))
            //将i-1 , j 给到 pre 得到下一轮的 i-1,j-1， 因为是内循环使用，继承了i-1 
            pre = tmp;
        }
    }
    fmt.Println(dp[len(str2)])
    return 

}
func min(a,b int ) int {
    if a < b {
        return a
    }
    return b
}

最小编辑代价

比较容易迷惑的地方

全站热榜