36 动态规划之编辑距离

问题描述：给你两个单词word1和word2，请你计算出将word1转换为word2所需要的最少操作数。插入一个字符删除一个字符替换一个字符；

暴力穷举法：将短的那一个串作为子串(长度s)，寻找在母串(长串长度p)共同字符最多的情况，即为(长度为m)则最后的修改长度为(s-m)修改短串所需操作次数，(p-s)删除长串多余的或增加短串长度使得与长串匹配。

public int minModifyNum(String word1,String word2)
{
if(word1.length()>=word2.length())
{
String shorter=new String(word2);
String longer=new String(word1);
}else
{
String shorter=new String(word1);
String longer=new String(word2);
}
int maxMach=Integer.MIN_VALUE;
for(int i=0;i<longer.length()-shorter.length()+1;i++)
{
int count=0;
for(int j=0;j<shorter.length();j++)
{
if(shorter.charAt(j)==longer.charAt(i+j))
{
count++;
}

}
maxMarch=Math.max(maxMarch,count);
}
return longer.length()-maxMarch;
}

动态规划求解：定义dp[i][j]为前i个字符串转换为j的操作数，如果i位置等于j位置，则为dp[i][j]=dp[i-1][j-1],如果不相等，则可以有删除该字符dp[i-1][j]+1的操作、改变该字符的操作dp[i-1][j-1]+1、增加一个字符的操作dp[i][j-1]+1使得j位置和增加的那个字符相等。

public int minChange(String word1,String word2)
{
int [][]dp=new int[word1.length()][word2.length()];
if(word1.charAt(0)==word2.charAt(0))
{
dp[0][0]=0;
}else
{
dp[0][0]=1;
}
for(int i=1;i<word1.length();i++)
{
for(int j=1;j<word2.length();j++)
{
if(word1.length()==word2.length())
{
dp[i][j]=dp[i-1][j-1];
}else
{
dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i-1][j-1]+1),dp[i][j-1]+1);
}
}
}
return dp[word1.length()][word2.length()];
}