字符串之间的最短距离

#include <iostream>
using namespace std;

//为了方便，将a和b的长度固定下来，这样就不用动态创建数组了
#define M 6
#define N 3
int dp[M][N] = {0};
/**
* 问题描述： 两个字符串如果可以根据添加，删除，修改一个字符串来变成另一个字符串，则
* 说这两个字符串距离为1. 现在给出两个字符串，求出他们之间的距离。
* abcehk和bdh的距离。
* 要将一个字符串变成另一个，这里假设将B变换成A，很明显这个问题有子结构。
* 要求f(m,n)，即字符串A与字符串B的距离：
* 如果a[m] == b[n]，那么这个距离就是其上一个状态，即f(m-1,n-1)。
* 如果a[m] != b[n]，
*	要么删除b[n]，这个时候问题变成f(m,n-1)
*	要么为B增加一个和a[m]相同的字符让其与A的结尾相同，这个时候问题变成f(m,n+1) = f(m-1,n)（因为末尾字符相同，故不考虑）。
*	要么修改b[n]为a[m]，这个时候问题变成求解f(m-1.n-1).
* 这些操作的代价都是1，主要是看子问题的代价，选择最小的。(DP特征)
* 
* 所以我们定义状态f(m,n)为长度为m的串A与长度为n的串B之间的距离。
* 然后定义状态转移方程为：
* f(m,n) = 
*	f(m-1,n-1),								a[m] == b[n]
*   min{f(m-1,n-1)，f(m,n-1)，f(m-1,n)}+1，	a[m]!=b[n]
* 自底向上求解，DP求解矩阵的第一行和第一列很容易初始化.
*/
int min(int x, int y, int z){
	if(x<y){
		if(x<z) return x;
		else return z;
	}
	else{
		if(y<z) return y;
		else return z;
	}
}

int getDistance(char *a, char *b){
	if(a==NULL || b==NULL) return 0;

	//初始化两个字符串的长度
	int a_len=M,b_len=N;

	//初始化第一行和第一列
	if(a[0] != b[0]) dp[0][0] = 1;
	else dp[0][0] = 0;
	
	for(int i=1;i<b_len;i++){ //第一行
		if(a[0] != b[i]) dp[0][i] = dp[0][i-1]+1;
		else dp[0][i] = dp[0][i-1];
	}
	for(int j=1;j<a_len;j++){ //第一列
		if(b[0] != a[j]) dp[j][0] = dp[j-1][0]+1;
		else dp[j][0] = dp[j-1][0];
	}

	//开始自底向上计算
	for(i=1;i<a_len;i++){
		for(j=1;j<b_len;j++){
			if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1];
			else{
				dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;
			}
		}
	}

	//打印出最短距离数组
	for(i=0;i<a_len;i++){
		for(j=0;j<b_len;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	return dp[M-1][N-1];
}

int main(){
	
	/**
	*  注意顺序，这里a作为列，b作为行
	*/
	char *a = "abcehk";
	char *b = "beh";

	cout<<getDistance(a,b)<<endl;
	return 0;
}