动态规划(最长公共子串)

/**
 * 最长公共子串
 * dp[i][j] 的值只可能有两种情况
 * 1.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串最后一个字符是不可能的，令dp[i][j]=0
 * 2.如果str1[i]==str2[j] 说明str1[i]和str2[j]可以作为公共子串的最后一个字符，所以令 dp[i][j] = dp[i-1][j-1]+1
 */
public class CommonString {
	public static void main(String[] args) {
		String str1="ABCE12F";
		String str2="EAEEF";
		char[] chs1 = str1.toCharArray();
		char[] chs2 = str2.toCharArray();
		int[][] dp = getDp(chs1,chs2);
		int max=0;
		for(int i = 0;i<dp.length;i++){
			for(int j = 0;j<dp[i].length;j++){
				if(max<dp[i][j])
					max = dp[i][j];
			}
		}
		System.out.println(max);
	}
	private static int[][] getDp(char[] chs1, char[] chs2) {
		int[][] dp = new int[chs1.length][chs2.length];
		for(int i=0;i<chs1.length;i++){
			if(chs1[i]==chs2[0])
				dp[i][0]=1;
		}
		for(int j=0;j<chs2.length;j++){
			if(chs1[0] == chs2[j])
				dp[0][j]=1;
		}
		for(int i=1;i<chs1.length;i++){
			for(int j=1;j<chs2.length;j++){
				if(chs1[i] == chs2[j])
					dp[i][j] = dp[i-1][j-1]+1;
			}
		}
		return dp;
	}
}