C语言实现字符串编辑距离算法

#include<stdio.h>

#include <string.h>

#define MAXX 51

#define MAXY 51 //问题表示

int m,n; //求解结果表示

int dp[MAXX][MAXY];

void solve()

{ int i,j;

dp[0][0]=0;

memset(dp,0,sizeof(dp)); for(i=1;i<=m;i++)

    dp[i][0]=i;   

for(j=1;j<=n;j++)

    dp[0][j]=j;

for(i=1;i<=m;i++)

{

    for(j=1;j<=n;j++)

    {

        if(s1[i-1]==s2[j-1])

            dp[i][j]=dp[i-1][j-1];

        else

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

    }

}  

printf("%d",dp[m][n]);

}

写出这个程序的状态方程内容：该程序的状态方程为：

dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符之间的编辑距离。

状态转移方程为：

当s1[i-1]等于s2[j-1]时，dp[i][j] = dp[i-1][j-1]，表示当前字符相等，不需要进行编辑操作。

当s1[i-1]不等于s2[j-1]时，dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])，表示当前字符不相等，可以通过插入、删除或替换操作将两个字符串变为相等，取操作次数最小的值。

初始状态为：

dp[0][0] = 0，表示两个空字符串之间的编辑距离为0。

dp[i][0] = i，表示将字符串s1的前i个字符变为空字符串的编辑距离为i，即需要删除i个字符。

dp[0][j] = j，表示将空字符串变为字符串s2的前j个字符的编辑距离为j，即需要插入j个字符。

最终的编辑距离为dp[m][n]，其中m为字符串s1的长度，n为字符串s2的长度。