最小编辑代价（动态规划）

深藏阁楼爱情的钟 2022-08-18 02:19 156阅读 0赞

![20151205205631477][]

代码实现：对于不同的要求，主要是找到求dp\[i\]\[j\]的规律。

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    #define MAX_LENGTH 50  //字符串的最大长度
    
    /*  求出dp[i][j] 代表从str1[0..i],变为str2[0..j]的最小代价
        为了方便计算。str1和str2字符串前都加上一个空格
     */
    int minCost(const char* str1, const char* str2,const int ic, const int dc, const int rc)
    {
        if (str1 == NULL || str2 == NULL)
        {
           return 0;
        }
    
        int rows = strlen(str1) + 1;
        int cols = strlen(str2) + 1;
        int dp[MAX_LENGTH][MAX_LENGTH] = {0};
    
        int i = 0, j = 0;
    
        /* 求出dp第一列 */
        for(i = 1; i < rows; i++)
        {
            dp[i][0] = i * dc;
        }
    
        /* 求出第一行 */
        for(j = 1; j < cols; j++)
        {
            dp[0][j] = j * ic;
        }
    
        /* 求出余下的dp数值 */
        for(i = 1; i < rows; i++)
        {
            for(j = 1; j < cols; j++)
            {
                if (str1[i-1] == str2[j-1]) //第一种情况，相同
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = dp[i-1][j-1] + rc; //替换
                }
    
                dp[i][j] = min(dp[i][j], dp[i][j-1] + ic); //插入
                dp[i][j] = min(dp[i][j], dp[i-1][j] + dc); //删除
            }
        }
    
        return dp[rows-1][cols-1];
    }
    
    
    
    int main()
    {
        char str1[] = "abc";
        char str2[] = "adc";
    
        cout << minCost(str1,str2,5,3,100) << endl;
    }

[20151205205631477]: /images/20220731/2ade003e469c479bbb86d3d9dd7aad11.png