#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; }