两个字符串
最长公共字串：相同的连续的序列有多长？
最长公共子序列：相同的当不一定连续的序列有多长？
DP解法：都是构造矩阵，
最长公共字串思路：在边界（行==0或者列==0）构造好之后，下一个元素要么是0（两个元素不同），要么是左上对角元素值+1。
以下摘自：http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html
假设两个字符串分别为s和t，s[i]和t[j]分别表示其第i和第j个字符(字符顺序从0开始)，再令L[i, j]表示以s[i]和s[j]为结尾的相同子串的最大长度。应该不难递推出L[i, j]和L[i+1,j+1]之间的关系，因为两者其实只差s[i+1]和t[j+1]这一对字符。若s[i+1]和t[j+1]不同，那么L[i+1, j+1]自然应该是0，因为任何以它们为结尾的子串都不可能完全相同；而如果s[i+1]和t[j+1]相同，那么就只要在以s[i]和t[j]结尾的最长相同子串之后分别添上这两个字符即可，这样就可以让长度增加一位。合并上述两种情况，也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。
最后就是要小心的就是临界位置：如若两个字符串中任何一个是空串，那么最长公共子串的长度只能是0；当i为0时，L[0,j]应该是等于L[-1,j-1]再加上s[0]和t[j]提供的值，但L[-1,j-1]本是无效，但可以视s[-1]是空字符也就变成了前面一种临界情况，这样就可知L[-1,j-1]==0，所以L[0,j]=(s[0]==t[j]?1:0)。对于j为0也是一样的，同样可得L[i,0]=(s[i]==t[0]?1:0)。
最长公共子序列思路：在边界（行==0或者列==0）构造好之后，下一个元素要么是左边或者上边元素的最大的那个（两个元素不同），要么是左上对角元素值+1（两个元素相同）。
这里两个LCS的DP解法的相同与不同之处：
相同：都是DP，都是以“两个元素作为公共字串/子序列的末尾元素时”出发求解。
不同：最长公共子序列还要考虑到不连续，所以当两个元素不同时，最长公共字串为0，因为这以这两个元素结尾的两个字符串不属于最长公共字串，其长度由对角保护就可以了。而最长公共子序列的长度必须继承下来，也就是矩阵中左边或者上边这两个元素的最大值。