51 Nod 1183 编辑距离（动态规划基础）

原题链接：1183 编辑距离

题目分析：这个最少的操作次数，通常被称之为编辑距离。“编辑距离”一次本身具有最短的意思在里面。因为题目有“最短”这样的关键词，首先我们想到的是 $BFS$ 。是的，当 $S$ 的距离为 $m, T$ 的距离为 $n$ 的时候，我们可以找到这样的操作次数的界限：

把 $T$ 中字符全删了，再添加 $S$ 的全部字符，操作次数 $m + n$ 。
把 $T$ 中字符删或加成 $m$ 个，再修改操作次数最多 $\left | n-m \right | + m$ 。

虽然，我们找到了这样的上界， $BFS$ 从实际角度并不可行，因为搜索空间是指数的，这取决于 $S$ 中的字符种类——具体的数量级不好估计。

根据LCS的思路，做两字符串的比较。 $f(i,j)$ 表示 $T$ 字符串在 $1%u2013i$ $- i$ ,于 $S$ 字符串在 $1 - j$ 时的最小改变量。
递推式如下： $f(i,j) = min(f(i - 1, j - 1) + same(i,j), f(i - 1,j ) + 1, f(i, j - 1) + 1)$
初始值： $f(0, j) = j , f(i, 0) = i$

代码如下：

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

using namespace std;

const int MAX = 1005;

int dp[MAX][MAX];

string a, b;

int main() {

	memset(dp, 0, sizeof(dp));

	cin >> a >> b;

	for (int i = 0; i <= a.length(); i++) dp[i][0] = i;

	for (int i = 0; i <= b.length(); i++) dp[0][i] = i;

	for (int i = 1; i <= a.length(); i++)

		for (int j = 1; j <= b.length(); j++)

			dp[i][j] = min(dp[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1),

                            min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));

	cout << dp[a.length()][b.length()] << endl;

	return 0;

}

巴特西

51 Nod 1183 编辑距离（动态规划基础）

最新文章

热门文章

巴特西

51 Nod 1183 编辑距离 （动态规划基础）

最新文章

热门文章

51 Nod 1183 编辑距离（动态规划基础）