[数据结构与算法]POJ 2988:计算字符串距离

“ Ctrl AC！一起 AC！”

题目：忘题戳这

分析：这是一道动规题，从小推大。设置一个动规二维数组，首先可以确定数组的一些基础值。

dp[i][0]=i，dp[0][i]=i ;因为一个字符串是空串，另一个是长度i的字符串，那他们的距离自然是i。

根据基础值，通过状态方程，推出dp[len1][len2]即可。那么状态方程分两种情况，第一种是字符串a的第i+1个元素等于字符串b的第j+1个元素，那么dp[i+1][j+1]=dp[i][j]，对吧。如果不同，那么dp[i][j]就是dp[i+1][j],dp[i][j+1],dp[i][j]中的最小值加一，为什么呢？因为题目说了可以删除字符或修改字符。dp[i+1][j]+1就是通过删除j+1这个元素后得到的距离，dp[i][j+1]+1就是删除i+1,dp[i][j]+1就是修改i+1或j+1使它们相同。由此如题。

说明一下，a[i],b[j]中的i,j是下标，他们对应第i+1,j+1个元素。

而dp[i+1][j+1]，就是对应第i+1，j+1个元素，所以，a[i],b[j]对应dp[i+1][j+1]。

AC代码：

#include<iostream>	
#include<cstring>
using namespace std;
int dp[1005][1005];
int main() {
	int t; cin >> t;
	while (t--) {
		memset(dp, 0, sizeof(dp));
		string a, b;
		cin >> a >> b;
		int len1 = a.length();
		int len2 = b.length();
		for (int i = 1; i <= len1; i++) dp[i][0] = i;//必要的初始值
		for (int i = 1; i <= len2; i++) dp[0][i] = i;
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j];//状态方程
				else dp[i + 1][j + 1] = min(min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1;
			}
		}
		cout << dp[len1][len2] << endl;
	}
	return 0;
}

感谢阅读！！！

“ Ctrl AC！一起 AC！”