动态规划——最长公共子序列

lintcode-77 描述
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

这道题可以看做最长连续公共子序列的升级版
首先看状态转移：
当A[m]=B[n]时，则LCSCount=f[m-1][n-1]+1
当A[m]≠B[n]时，则LCSCount=min(f[m-1][n],f[m][n-1])

    public static int longestSubstringSequence(String A,String B){
    	
    	int f[][] = new int[A.length()+1][B.length()+1];	
    	for (int i = 1; i <= A.length(); i++) {
			for (int j = 1; j <= B.length(); j++) {
				if(A.charAt(i-1)==B.charAt(j-1)){
					f[i][j] = f[i-1][j-1]+1;
				}
				if(A.charAt(i-1)!=B.charAt(j-1)){
					f[i][j]=Math.max(f[i-1][j], f[i][j-1]);
				}
			}
		}

longestSubstringSequence("ABCDRAEA","BRAADE");

输出

0 0 0 0 0 0 0
0 0 0 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 2 2
0 1 2 2 2 2 2
0 1 2 3 3 3 3
0 1 2 3 3 3 4
0 1 2 3 4 4 4

心得：求解动态规划的矩阵形式时，初始化条件要处理边界。这里通过增加一列的方式来避免边界处理。