P1532 字符串编辑距离 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2026年2月26日 12:42

字符串编辑距离题解：

P1532

回复 0 | 赞 11 | 浏览 197

#include<bits/stdc++.h> using namespace std; const int N = 1010; int dp[N][N];//dp[i][j]:将a的前i个字符变成b的前j个字符所需的最短步数； int my_min(int a, int b, int c){ int res = min(a,b); res = min(res,c); return res; } int main(){ string a,b; cin>>a>>b; for(int j = 0; ...

2025年3月23日 21:37

字符串编辑距离题解：暴力，有一说一这题真不好想，之前没做过的话考场很

P1532

回复 0 | 赞 23 | 浏览 1.2k

#include <bits/stdc++.h> using namespace std; int main() { string str1, str2; cin >> str1 >> str2; int a = str1.size(), b = str2.size(); vector<vector<int>> dp(a+1, vector<int&g...

2024年3月20日 21:38

字符串编辑距离题解：

P1532

回复 0 | 赞 43 | 浏览 1.9k

DP基本问题要明白DP数组的含义，即前i/j个字符的字符串编辑距离递推公式的含义以及dp数组的初始化 #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; int minDistance(string word1,string word2){ int m = word1.size(); int n = word2.size(); ...

2023年2月13日 11:19

计算字符串编辑距离通解方法

P1532

回复 0 | 赞 29 | 浏览 5.0k

原理：给出一个初始化矩阵，逐位比较两个字符串，待修改的矩阵对应为行，被比较的矩阵对应位列若字符串对应的位相同，则让该矩阵位直接让这一位的矩阵的等于左上对角的值否则，有三种情况，分别是： ①：等于上面矩阵位加一 ②：等于左上角矩阵位加一 ③：等于左边矩阵位加一最后该矩阵位取上面三种情况中最小的一中。最右下角的一位保存的就是字符串编辑距离 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=1e9; const int ...

2022年7月11日 17:50

套公式题解（C++dp）

P1532

回复 0 | 赞 29 | 浏览 7.3k

#include<bits/stdc++.h> using namespace std; const int MAX = 1005; int dp[MAX][MAX]; string a,b; //dp[i][j]是指字符串1中的前i个字符和字符串2中的前j个字符的编辑距离 int main(){ cin>>a>>b; int lena = a.length(); int lenb = b.length(); memset(dp, 0, sizeof(dp)); //initia...

2022年3月20日 15:55

C++

P1532

回复 0 | 赞 0 | 浏览 5.5k

2020年5月28日 09:39

经典dp

P1532

回复 0 | 赞 10 | 浏览 11.1k

#define ll long long #define vec vector<int> #define inf 0x3f3f3f3f #define MAX 1005 #define P pair<ll,ll> #define MOD 1000000 int main() { string a, b; int dp[MAX][MAX]; while (cin >> a >> b) { a = ' ' + a, b = ' ' + b; int l1 = a.size(), l...

题目字符串编辑距离

题解数量7

发布题解在线答疑

热门题解

1 字符串编辑距离题解：

2 计算字符串编辑距离通解方法

3 套公式题解（C++dp）

4 字符串编辑距离题解：暴力，有一说一这题真不好想，之前没做过的话考场很难想出来

5 字符串编辑距离题解：

6 经典dp

7 C++