936-最小编辑代价
2022/1/5 23:03:44
本文主要是介绍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-最小编辑代价的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-11有哪些好用的家政团队管理工具?
- 2025-01-11营销人必看的GTM五个指标
- 2025-01-11办公软件在直播电商前期筹划中的应用与推荐
- 2025-01-11提升组织效率:上级管理者如何优化跨部门任务分配
- 2025-01-11酒店精细化运营背后的协同工具支持
- 2025-01-11跨境电商选品全攻略:工具使用、市场数据与选品策略
- 2025-01-11数据驱动酒店管理:在线工具的核心价值解析
- 2025-01-11cursor试用出现:Too many free trial accounts used on this machine 的解决方法
- 2025-01-11百万架构师第十四课:源码分析:Spring 源码分析:深入分析IOC那些鲜为人知的细节|JavaGuide
- 2025-01-11不得不了解的高效AI办公工具API