最小编辑代价（编辑距离问题改进版）

谁借莪１个温暖的怀抱￠ 2022-10-16 09:45 157阅读 0赞

#### 题目描述 ####

给定两个字符串str1和str2，再给定三个整数ic，dc，rc，分别代表插入、删除、替换一个字符的代价，返回将str1编辑成str2的最小代价。

该题是基于经典动态规划问题编辑距离的改进版[编辑距离问题][Link 1]

#### 输入输出样例 ####

**输入1**

> str1=“abc” str2=“adc” ic=5 dc=3 rc=2

从"abc"编辑到"adc"把b替换成d代价最小，为2；  
**输出1**

> 2

**输入2**

> str1=“abc” str2=“adc” ic=5 dc=3 rc=10

从"abc"编辑到"adc"，先删除b再插入d代价最小，为8；  
**输出2**

> 8

#### 思路解析 ####

**动态规划问题大多都是求最值问题，求最值意味着要先穷举才能求最值。**

**约定**

约定DP表即二维数组`A[i][j]`,表示由字符串A的前`i`位变成字符串B的前`j`位，所形成的两个字符串变换所需要的最小编辑距离。

**初始化**

如果两个字符串中有一个字符串是空，那么另外一个字符串变成它需要插入操作即可。

for(i=0;i<=s1.length();i++)
    {
        
        a[i][0] = i*ic;
    }
    for(j=0;j<=s2.length();j++)
    {
        
        a[0][j] = j*ic;
    }

**状态转移方程**

出了上述初始化部分，我们要考虑四种情况：  
1.如果字符串S1和S2的末尾字符相同，即`S1[i-1]==S2[j-1]`，那么代表《前i个与前j个组成的字符串代价》与《前i-1和前j-1个组成的字符串代价 》是相同的。  
2.如果末尾不相同，那么就意味着需要进行变换，可以由不同的情况通过插入、删除、替换三种操作来实现，而题目要求找最小代价，那么求这三种对应的最小操作就行。

*  替换：`a[i-1][j-1]+uc`
 *  插入/删除(插入或删除都可以)： `a[i-1][j]+dc,a[i][j-1]+ic`

#### C++ 实现 ####

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    void printDP(int a[100][100],int q,int p)
    {
        
    	int i,j;
    	for(i=0;i<q;i++)
    	{
        
    		for(j=0;j<p;j++)
    		{
        
    			cout<<a[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    }
    // DP表要当代价的
    int minPrice(string s1,string s2,int ic,int dc,int uc)
    {
        
    	// i j 代表两个字符串的前n个字符比对 
        int a[100][100];
        int i,j;
        // base case 插入所需代价
        for(i=0;i<=s1.length();i++)
        {
        
            a[i][0] = i*ic;
        }
        for(j=0;j<=s2.length();j++)
        {
        
            a[0][j] = j*ic;
        }
        // 都不是空串的情况
        for(int i=1;i<=s1.length();i++)
        {
        
            for(int j=1;j<=s2.length();j++)
            {
        
                // 若末尾两字符相同
                if(s1[i-1]==s2[j-1])
                {
        
                    // 不需要进行任何操作，即前i个与前j个组成的字符串与前i-1和前j-1个组成的字符串代价是相同的
                    a[i][j]==a[i-1][j-1];
                }else{
        
                    // 进行插入删除编辑
                    a[i][j]=min(a[i-1][j-1]+uc,min(a[i-1][j]+dc,a[i][j-1]+ic));
                
                }
                
            }
        }
        printDP(a,s1.length(),s2.length());
        return a[s1.length()-1][s2.length()-1];
    }
    
    int main()
    {
        
        cout<<minPrice("abc","adc",5,3,10);
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210529114506293.png]

[Link 1]: https://blog.csdn.net/weixin_43889841/article/details/102676583
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221014/353522bf47d94bd2b3fbf620d0e8f214.png
[20210529114506293.png]: /images/20221014/8e3f4e3def3d4c62bbedac261dc65fc4.png