主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
答疑区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
Barry Liu
2024年3月20日 21:38
字符串编辑距离 题解:
P1532
回复 0
|
赞 0
|
浏览 656
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(); ...
blackevil
2023年2月13日 11:19
计算字符串编辑距离通解方法
P1532
回复 0
|
赞 0
|
浏览 3.7k
原理: 给出一个初始化矩阵,逐位比较两个字符串,待修改的矩阵对应为行,被比较的矩阵对应位列 若字符串对应的位相同,则让该矩阵位直接让这一位的矩阵的等于左上对角的值 否则,有三种情况,分别是: ①:等于上面矩阵位加一 ②:等于左上角矩阵位加一 ③:等于左边矩阵位加一 最后该矩阵位取上面三种情况中最小的一中。 最右下角的一位保存的就是字符串编辑距离 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=1e9; const int ...
chiangtau
2022年7月11日 17:50
套公式题解(C++dp)
P1532
回复 0
|
赞 3
|
浏览 6.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
|
浏览 4.9k
csYfZhang
2020年5月28日 09:39
经典dp
P1532
回复 0
|
赞 0
|
浏览 9.6k
#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...
题目
字符串编辑距离
题解数量
5
发布题解
热门题解
1
套公式题解(C++dp)
2
计算字符串编辑距离通解方法
3
经典dp
4
C++
5
字符串编辑距离 题解: