考虑到动态地计划最长的公共子串，如果有以下两个字符串的话，根据最长公共子串的定义，可以知道求其最长公共子串的FRAMEFAMILY的最长字符串明显为： FAM
那么怎么求呢？ 怎么用代码实现？ 这里先分析一下求法吧。
比如给字符串一个序号一个串叫A串（FRAME），一个叫B串（FAMILY）
字符串| F | R | A | M | E |B字符串| f|a|m|I|l|y|http://www.Sina.com /
step1:考虑到首字母f相等，f子序列的长度加1的话问题就是求出a序列(RAME )，b序列) AMILY )的最长子序列的问题。
a字符串：| R | A | M | E |B字符串：| A | M | I | L | Y | step2:如果它们不相等呢？ 一个方法是继续求a列和b列。首先可以考虑采用递归来解决另一种方法是去掉a列和b列不相等的首字母(r )
使问题成为： A字符串：| A | M | E |B字符串：| A | M | I | L | Y |的另一种方法是删除b字符串和a字符串不相等的首字母(a )
将问题设为： A字符串：| R | A | M | E |B字符串：| M | I | L | Y |时，不知道用2和3中的哪一种方法求出的结果更好。 因此需要（这里显然是不行的， 因为继续求得结果还是不相等）的那个。
那么，问题的分析到此结束了。 给你代码吧。
/* *最长公共子串*/public class test_1 {static int最长公共子串_递归(String A， String B ) (/字符串长度为0时，公共子串长度为0if(a.length )===(if ) a.charat(0)=b.charat (0) ) /开头字符相等时) /在求解子问题时， 在构思末尾加上1 )如果字符相等，对子序列长度加1 ) return最长公共子序列__递归) A.substring(1)加1 ) }else {//如果字符不相等//2和3中B.substring(1)1)、最长公共子序列_递归) A.substring(1)、} publicstaticvoidmain (string [ ] args )//两个字符串string a String B='FAMILY '； int num=最长公共子序列_递归(a，b )； System.out.println ('最长公共子序列长度为：' num )； }根据递归时间复杂度代码可知，该递归时间复杂度非常高。取其中最大
时间的复杂性主要来源于这一行的代码。
return Math.max (最长公共子序列_递归(a，b.substring(1)，最长公共子序列_递归) A.substring(1) 1，b ) )； 我们知道近似于2的N次方是爆炸性的订单。 如果a列和b列的长度达到十数，求出可能需要几秒钟。
2的N次方
其实，请分析一下上面考虑的一些情况。
字符相等如果字符不相等，则假设将两个字符串分别放在一张图的x轴和y轴上。
文字相等时剪切a和b时得到的结果(也就是左上角的1 )即可。 文字不相等时，取减法运算a的结果和减法运算b的结果的最大值(左边和上边的最大值)即可。那有没有一种更好的方法呢？
思想解决了的话，代码就很简单了。
坐代码吧！
//注：这里不写主函数。 此函数执行/** *以确定最长公共子序列-动态规划算法* @param str1 A列* @param str2 B列* @ return */publicstaticintlcs (stringstr1int //初始矩阵intmymap [ ] [ ]=new int [ str1len1] [ str2len1]； //要记录最长字符串的源//上为2，左为3，对角为1in TD [ ] [ ]=new int [ str1len1] [ str2len1]； //开始遍历计算for (inti=1； i str1Len 1； I ) for(intj=1； j str2Len 1； j ) ) /如果两个字符相等，则获取上次匹配并使用1if(str1.charat(I-1 )==str2.charat(j-1 ) ) mymap[I][j]=mymap[I-1] (else ) /否则，剪切第一个串，计算出第二个串的最大值的if ) mymap[I-1][j]mymap[I][j-1] ) mymap [ I ] [ j ]=mymap [ j ] }else {d[i][j]=3； myMap[i][j]=myMap[i][j - 1]； }}}}/计算结束//输出路径矩阵System.out.println ('路径矩阵d为： ) )； for(intI=0； i str1Len 1； I ) for(intj=0； j str2Len 1； j ) (system.out.print ) d[I][j]，')； }System.out.println (； //输出最大子串//可以从路径矩阵中逆向查找最大子串由哪个字符构成的int tFind=10； int i=str1Len； int j=str2Len； stringbufferlscstr=new string buffer (' ' )； wile(tfind )！=0) {tFind=d[i][j]； if(tfind==3) )//来源于左边的j----； (elseif ) tfind==2) ) /源为上边I----； }elseif(tfind==1) lscstr.append ) str2.charat(j-1 )； I----； j----； //输出最长序列//是以相反的方向制作的，所以字符串System.out.println ('最大子序列是： ' LSCStr.reverse ) ) ) ) ) ) ) ) //最大子序列长度return myMap[str1Len][str2Len]； }关于动态规划的时间复杂度，从代码中可以看出动态规划的时间复杂度与递归相比大幅减少。
33558www.Sina.com/(n(其中n是a字符串长度，m是b字符串长度) )。
时间的复杂性主要来源于这两行代码。
for(intI=1； i str1Len 1； I ) for(intj=1； j str2Len 1； j ) (空间复杂度于是可以初始化矩阵为：)我们使用了两个二维数组来存储路径源和结构矩阵。 ）
近似于N*M
这个句子到此结束。 谢谢您的阅读。 欢迎发表评论。