936-最小编辑代价

本文主要是介绍936-最小编辑代价，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目如下

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
输入：“abc”,“adc”,5,3,2
输出：2

解题代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int minEditCost(string str1, string str2, int ic, int dc, int rc)
{

    /*
            1.dp[i][j] 表示str1的前i个字符编辑成str2的前j个字符的最小代价
            "abc","adc",5,3,2     ab   d       a     d
            2.str1[i] == str2[j]   相等的话 那么就是 dp[i][j] = dp[i-1][j-1] 的代价
            str1[i] != str2[j]  那么分三种情况     1.插入一个字符dp[i][j] = dp[i][j-1] + ic;
                                                  2.删除一个字符 dp[i][j] = dp[i-1][j]+dc;
                                                  3.修改一个字符 dp[i][j] = dp[i-1][j-1]+rc; 求出三者的最小
            3.初始状态:"" --- >   str2    插入字符
                     str1---->""    删除字符
    */
    int len1 = str1.length();
    int len2 = str2.length();
    if (len1 == 0)
    {
        return len2 * ic;
    }
    if (len2 == 0)
    {
        return len1 * dc;
    }

    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 0; i <= len2; ++i)
    {
        dp[0][i] = i * ic;
    }
    for (int i = 0; i <= len1; ++i)
    {
        dp[i][0] = i * dc;
    }
    for (int i = 1; i <= len1; ++i)
    {
        for (int j = 1; j <= len2; ++j)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = min(min(dp[i][j - 1] + ic, dp[i - 1][j] + dc),
                    dp[i - 1][j - 1] + rc);
            }
        }
    }
    return dp[len1][len2];
}

这篇关于936-最小编辑代价的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！