引言
上篇博客我们学习了动态规划的两个入门案例，今天我们继续分析两个经典问题:最长回文和字串相似度问题，后者可以通过字串的编辑距离来描述。下面看各自的分析。
最长回文问题
回文就是字串是镜像对称的,下面我们分析它的解能否通过迭代得到。设X的子串{xj,...,xi}(记为X(j,i))为回文，那么下一步将边界向两边扩散，判断X(j-1,i+1)是否为回文:
1>如果X[j-1]==X[i+1],则X(j-1,i+1)为回文,也就是说X(j-1,i+1)是否为回文决定于X(j,i)的结果;
2>如果X[j-1]!=X[i+1],则X(j-1,i+1)不为回文。
因此这个问题可以通过上一迭代的求解得到，动态规划方案可行。下面我们讨论一下迭代边界:
1.当i==j时,只有一个字符,为回文。
2.当i-j==1时,只有两个字符,X[i]=X[j]则为回文，反之不是。
由此得到迭代公式:
有了迭代公式，代码就好写了:
package com.qicode.algorithmlearning.dp;
/**
* Created by chenming on 2018/6/22
* 最长回文字串问题
* 迭代方程:c[j][i] 记录从索引j到i的字串是否为回文
* <p>
* 1.当i=j时表示只有一个元素,c[j][i]==true
* 2.当i-j=1时:字串长度为2，c[j][i]为s[i]和s[j]是否相等，即c[j][i]=(s[i]==s[j])
* 3.当i-j > 1时:
* s[i] != s[j],则c[j][i]=false
* s[i] = s[j],则判断字串[j+1, i-1]是否为回文，即c[j+1][i-1]=(s[i]==s[j])&&c[j+1][i+1]
*/
public class Palindrome {
public static String longestPalindromeStr(String s) {
int n = s.length();
boolean[][] c = new boolean[n][n];
int maxlen = 1;//最长回文子串长度
int startIndex = 0;//最长回文起点
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {//从j到i迭代
if (i - j < 2) {
c[j][i] = (s.charAt(i) == s.charAt(j));
} else if (i - j > 1) {
c[j][i] = (s.charAt(i) == s.charAt(j)) && c[j + 1][i - 1];
}
if (c[j][i] && maxlen < i - j + 1) {
maxlen = i - j + 1;
startIndex = j;
}
}
}
String result = s.substring(startIndex, startIndex+maxlen);
System.out.println("====最长回文====");
System.out.println(result);
return result;
}
}
测试代码:
@Test
public void testPalindromeStr(){
Palindrome.longestPalindromeStr("badaaaadcab");
}
打印结果:
====最长回文====
daaaad
最短字串编辑距离
问题描述
LeetCode72:
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
最短字串编辑距离是指将一个字串变换为另一个字串所需要的最小编辑操作步数。字串X与Y有多种对齐方式，在每种对齐方式下，各个对齐位上做N步删除、替换或者插入操作，X才转换成Y，这个操作步数就是编辑距离,如比较FAMILY和FRAME:
1> F _ A M I L Y
F R A M E
编辑流程:插入R-->I替换为E-->删除L-->删除Y，编辑距离4
2> - F A M I L Y
F R A M E
编辑流程:插入F-->F替换为R-->I替换为E-->删除L-->删除Y,编辑距离5。
...
那么如何从这些情况中找到最短的编辑流程呢？
问题分析:
还是先分析问题能不能通过迭代实现:
为了求串X(m)={x1,x2,...,xm}和Y(n)={y1,y2,y3,...y(n)}的编辑距离，我们可以先求它们前缀X(i)和Y(j)的编辑距离。假设c[i][j]是X(i)和Y(j)的编辑距离，那么它们无论怎么对齐，其右侧只有三种对齐方式:
1> x[1],x[2],.......x[i-1],x[i]
y[1],y[2],.......y[j], -
此时删除x[i]即可,有c[i][j]= c[i-1][j]+1
2> x[1],x[2],.......x[i-1],--
y[1],y[2],.......y[j-1],y[j]
此时删除y[j]即可,有c[i][j]= c[i-1][j]+1
3>右边对齐:
x[1],x[2],.......x[i]
y[1],y[2],.......y[j],
如果x[i]=y[j]则不用编辑,d[i][j]= d[i-1][j-j];如果不相等则c[i][j]= c[i-1][j-j]+1。
综上分析c[i][j]取三种情况的最小值即可,迭代公式如下:
1.s[i]=s[j],c[i][j]=c[i-1][j-1],编辑距离不变
2.s[i]=s[j],c[i][j]=min(c[i][j-1]+1,c[i-1][j]+1, c[i-1][j-1]+1),表示本次需要做一次操作，去三种情况的最小值，结合前面的分析，每一步操作判定如下:
1>取c[i][j-1]表示插入s2[j];
2>取c[i-1][j]表示删除S1[i];
3>去c[i-1][j-1]表示替换s1[i]为s2[j]
具体代码如下:
package com.qicode.algorithmlearning.dp;
/**
* Created by chenming on 2018/6/23
* 最小编辑距离
* 迭代方程c[i][j]表示S1的字串S1[0-i]和S2[0-J]的编辑距离
* 1.当S1[i]=S[j]时，c[i][j]=c[i-1][j-1],字符相等距离不变
* 2.当S1[i]!=S2[j]时,c[i][j]=min(c[i][j-1]+1,c[i-1][j]+1, c[i-1][j-1]+1),(来源左侧)取c[i][j-1]表示插入S2[j]，（来源上侧）取c[i-1][j]表示删除S1[i]
*/
public class MinEditDistance {
public static int getMinEditDistance(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
//极端条件限制
if (s1.length() == 0) {
return len2;
}
if (s2.length() == 0) {
return len1;
}
int[][] c = new int[len1 + 1][len2 + 1];//初始化第0行为0-len2,0列为0-len1，这表示空串和它们的编辑距离,
// 所以行列多一行,剩下的才是迭代矩阵
for (int i = 0; i <= len2; i++) {
c[0][i] = i;
}
for (int j = 0; j <= len1; j++) {
c[j][0] = j;
}
int dif = 0;
//开始迭代
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
c[i][j] = c[i - 1][j - 1];
} else {
int temp = Math.min(c[i - 1][j], c[i][j - 1]) + 1;
c[i][j] = Math.min(temp, c[i - 1][j - 1] + 1);
}
}
}
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
System.out.print(c[i][j] + ", ");
}
System.out.println("");
}
System.out.println("=====编辑过程======");
int startX = len1;
int startY = len2;
while (startX >= 1 && startY >= 1) {
if (s1.charAt(startX - 1) == s2.charAt(startY - 1)) {//字符相等啥也不做,左上方移动
startX--;
startY--;
} else {
int upVal = c[startX - 1][startY] + 1;//上方的值
int leftVal = c[startX][startY - 1] + 1;//左边的值
int upLeft = c[startX - 1][startY - 1] + 1;//左上方的值
if (c[startX][startY] == upVal) {//来源上侧,取c[i-1][j]表示删除S1[i]
System.out.println("删除" + s1.charAt(startX - 1));
startX--;
} else if (c[startX][startY] == leftVal) {//(来源左侧)取c[i][j-1]表示插入S2[j]
System.out.println("插入" + s2.charAt(startY - 1));
startY--;
} else if (c[startX][startY] == upLeft) {//来源左上表示替换s1[i]为s2[j]
System.out.println("替换" + s1.charAt(startX - 1) + "为" + s2.charAt(startY - 1));
startX--;
startY--;
}
}
}
return c[len1][len2];
}
}
编辑过程为逆序打印。只要理解了上面的分析思路，代码很好理解，这里不在详细说明了。
通过这两篇博客，我们知道动态规划的核心思想就是站在“规模较小问题已经求解”的台阶上,求解规模较大问题,分析出迭代公式，这也是动态规划的难点。目前我也只是入门，水平有限，力求不误人子弟，还望见谅！以后有其他经典案例，我也会不定期分享。
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
