动态规划算法

1.最长公共子串： 转自：http://www.yuanma.org/data/2006/0723/article_1215.htm

算法思想

求字符串str1,str2的最长公共子串的长度。

定义二元函数函数f(m,n)：分别以str1[m],str2[n]结尾的连续公共子串的长度

而对于f(m+1,n+1) 有以下两种情况

1.str1[m+1] != str2[n+1],则有f(m+1,n+1) =0

2.str1[m+1] == str2[n+1],则有f(m+1,n+1) = f(m,n) + 1

另外f(0,j) = 0(j>=0)

       f(j,0) = 0 (j>=0)

输出结果：

String:

    1. blog.csdn.net

    2. csdn.blog

         c   s   d   n   .   b   l   o   g  

    0   0   0   0   0   0   0   0   0   0  

b   0   0   0   0   0   0   1    0   0   0  

l   0   0   0   0   0   0   0   2    0   0  

o   0   0   0   0   0   0   0   0   3    0  

g   0   0   0   0   0   0   0   0   0   4   

.   0   0   0   0   0   1   0   0   0   0  

c   0   1    0   0   0   0   0   0   0   0  

s   0   0   2    0   0   0   0   0   0   0  

d   0   0   0   3    0   0   0   0   0   0  

n   0   0   0   0   4    0   0   0   0   0  

.   0   0   0   0   0   5    0   0   0   0  

n   0   0   0   0   1    0   0   0   0   0  

e   0   0   0   0   0   0   0   0   0   0  

t   0   0   0   0   0   0   0   0   0   0  

Java实现：

	public static String getValue(String str1,String str2){
		int maxi = 0;
		int max = 0;
		
		int[][] f = new int[str1.length()+1][str2.length()+1];
		for(int i=0;i<=str2.length();i++	){
			f[0][i] = 0;
		}
		
		for(int i=0;i<=str1.length();i++){
			f[i][0] = 0;
		}
		
		for(int i=0;i<str1.length();i++){
			for(int j=0;j<str2.length();j++){
				if(str1.charAt(i)==str2.charAt(j)){
					f[i+1][j+1] = f[i][j] + 1;
					if(max<f[i+1][j+1]){
						max = f[i+1][j+1];
						maxi = i+1;
					}
				}else{
					f[i+1][j+1] = 0;
				}
			}
		}
		
		
		return str1.substring(maxi-max,maxi);
}

2.