关于动态规划：
动态规划最重要的是找到可递推的子问题，然后列出递推公式，最后搜索填表即可。
表空间大小一般是$O(N^2)$级别。但一般来说，由于递推只与前一行有关，所以可优化至O(N)。
给出两个长度分别为n1, n2的字符串S1， S2, 关于他们的最长公共子串，DP方程如下：
L[i,j] = ( S1[i] == s2[j] ? L[i-1,j-1]+1 : 0 );
其中L[i,j]表示S1， S2中以第i 和第j 个字符结尾的公共子串的长度。
我们把n1 * n2的表空间遍历一遍就可得出最长公共子串。代码如下：
public String DPlengthOfLongestCommonSubstring(String s1, String s2){
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
return "";
}
int start = 0;
int maxLen = 0;
int [][] table = new int[s1.length()][s2.length()];
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
if (i == 0 || j == 0){
if (s1.charAt(i) == s2.charAt(j)){
table[i][j] = 1;
}
if (table[i][j] > maxLen){
maxLen = table[i][j];
start = i;
}
}else {
if (s1.charAt(i) == s2.charAt(j)){
table[i][j] = table[i-1][j-1] + 1;
}
if (table[i][j] > maxLen){
maxLen = table[i][j];
start = i + 1 - maxLen;
}
}
}
}
return s1.substring(start, start + maxLen);
}
由于只要填表，而后一行值只与前一行有关，因此空间可以省到O(N)。还是DP惯用的一前一后防覆盖法。
/**
* 只用O(N)额外空间
* @param s1
* @param s2
* @return
*/
public String DPlengthOfLongestCommonSubstring2(String s1, String s2){
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
return "";
}
int start = 0;
int maxLen = 0;
int[] table = new int[s2.length()];
for (int i = 0; i < s1.length(); i++) {
for (int j = s2.length()-1; j > - 1; j--) {
if (i == 0 || j == 0){
if (s1.charAt(i) == s2.charAt(j)){
table[j] = 1;
}else {
table[j] = 0;
}
if (table[j] > maxLen){
maxLen = table[j];
start = i;
}
}else {
if (s1.charAt(i) == s2.charAt(j)){
table[j] = table[j-1] + 1;
}else {
table[j] = 0;
}
if (table[j] > maxLen){
maxLen = table[j];
start = i + 1 - maxLen;
}
}
}
}
return s1.substring(start, start + maxLen);
}