搜索
简帛阁>技术文章>AcWing902 最短编辑距离

AcWing902 最短编辑距离

给定两个字符串 A 和 B,现在要将 A 经过若干操作变为 B,可进行的操作有:

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出,将 A 变为 B 至少需要进行多少次操作。

输入格式
第一行包含整数 n,表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m,表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大写字母。

输出格式
输出一个整数,表示最少操作次数。

数据范围
1≤n,m≤1000
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int dp[N][N];
char a[N], b[N];
int n, m;

int main() {<!-- -->
	cin >> n >> a + 1 >> m >> b + 1;
	
	for (int i = 0; i <= m; i++)dp[0][i] = i;//假设a中没有字母 和b中i个字母匹配的最少次数是i
	for (int i = 0; i <= n; i++)dp[i][0] = i;//假设b中没有字母 为使a和b匹配的操作最少次数是i

	for (int i = 1; i <= n; i++) {<!-- -->
		for (int j = 1; j <= m; j++) {<!-- -->
			dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);//进行增加或删除操作
			if (a[i] == b[j])dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);//如果当前字符相同则无需进行操作
			else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);//否则 进行改动操作
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}
给定两个字符串A和B,现在要将A经过若干操作变为B,可进行的操作有:删除–将字符串A中的某个字符删除。插入–在字符串A的某个位置插入某个字符。替换–将字符串A中的某个字符替换为另一个字符。现在请你求出
题目描述给定一张n个点的带权无向图,点从0∼n−1标号,求起点0到终点n−1的Hamilton路径。Hamilton路径的定义是从0到n−1不重不漏地经过每个点恰好一次。输入格式第一行输入整数n。
利用动态规划算法,实现编辑距离的计算。代码如下:encoding:utf8author:xujindate:Nov12,2012EditDistancetofindtheminimumcostby
给定一个单词列表和两个单词word1和word2,返回列表中这两个单词之间的短距离。来源:力扣(LeetCode)链接:https://leetcodecncom/problems/shortes
include<bits/stdc++h>defineN1000100usingnamespacestd;structnode{intl,r;intdata;}e[4*N];intn,m,
短路问题一、单源短路(一个点到所有点的短距离)1、所有边的权重都为正n个点,m个边(1)朴素dijkstraO(n^2)适合稠密图,O(n^2)O(m)算法步骤:①初始化距离dis[1]0,di
一种新型疾病,COWVID19,开始在全世界的奶牛之间传播。FarmerJohn正在采取尽可能多的预防措施来防止他的牛群被感染。FarmerJohn的牛棚是一个狭长的建筑物,有一排共N个牛栏。有些牛栏
首先维护一张两点之间的表tmp:ab12insertintotmpselect*fromtmptwherenotexists(select1fromtmpwheretb{a}andta{b})andn
ACWING1175大半连通子图缩点+DAGDP1175大半连通子图AcWing题库因为一个强连通分量中所有点可互相到达,所以一个强连通分量必然是一个半联通子图缩点后,求最长链即可(此处的最长指链
Givenalistofwordsandtwowordsword1andword2,returntheshortestdistancebetweenthesetwowordsinthelistExam