?

#include<iostream> #include<string> #include<algorithm> using namespace std;const int MAX = 1001; int MaxLen[MAX][MAX];int maxLen(string str1, string str2) {int len1 = str1.length();//行int len2 = str2.length();//列for (int i = 0; i < len1; i++)MaxLen[i][0] = 0;for (int j = 0; j < len2; j++)MaxLen[0][j] = 0;for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++){if (str1[i - 1] == str2[j - 1])MaxLen[i][j] = MaxLen[i - 1][j - 1] + 1;else{int temp = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);MaxLen[i][j]=max(temp,MaxLen[i-1][j-1]);}}}return MaxLen[len1][len2]; } int main() {string str;int count = 0;while (cin >> str){int len = str.size();if (len == 1){cout << 1 << endl;continue;}string revs = str;reverse(revs.begin(), revs.end());int max_len = maxLen(str, revs);cout << len - max_len << endl;}return 0; } View Code

?

?

參考：http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html

? ? ? ? ?這是很經(jīng)典的動(dòng)態(tài)規(guī)劃問題。注意其中二維動(dòng)態(tài)數(shù)組內(nèi)存的分配和釋放。

? ? ? ? ?

int edit(const string str1, const string str2) {int m = str1.size();int n = str2.size();//定義一個(gè)m*n的二維數(shù)組int **ptr = new int*[m+1];for (int i = 0; i < m + 1; i++)ptr[i] = new int[n + 1];//初始化for (int i = 0; i < m + 1; i++)ptr[i][0] = i;for (int j = 0; j < n + 1; j++)ptr[0][j] = j;for (int i = 1; i < m + 1; i++){for (int j = 1; j < n + 1; j++){int d;int temp = min(ptr[i - 1][j] + 1, ptr[i][j - 1] + 1);if (str1[i - 1] == str2[j - 1])d = 0;elsed = 1;ptr[i][j] = min(temp, ptr[i - 1][j - 1] + d);}}int dis = ptr[m][n];//注意釋放內(nèi)存for (int i = 0; i < m + 1; i++){delete[] ptr[i];ptr[i] = nullptr;}delete[] ptr;ptr = nullptr;return dis;} int main() {string str1;string str2;cin >> str1;cin >> str2;edit(str1, str2);return 0; } View Code

?

?

2017騰訊實(shí)習(xí)題，求最長公共子串的：http://www.nowcoder.com/test/question/done?tid=4822903&qid=44802

?

同樣用DP求子符串與其反串的最長公共子串的長度，然后用總長減去公共子串的長度即可。

?

轉(zhuǎn)載于:https://www.cnblogs.com/573177885qq/p/5832328.html

總結(jié)

以上是生活随笔為你收集整理的编辑距离及编辑距离算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。