【动态规划】最长公共子序列问题

问题描述：

　　字符串s1=BDCABC，字符串s2=ABCBDAB；求它们的最长公共子序列。

定义dp[ i ][ j ] :s1的前 i 个字符串和s2前 j 个字符串的最长公共子序列长度。

以下讨论三种情况：

　　s1[ i ] == s2[ j ]　　s1的第 i 个字符等于s2的第 j 个字符

dp[ i ][ j ] = dp[ i-1 ][ j-1 ]+1;

　　s1[ i ] != s2[ j ]       比较  前 i-1 个字符串与前 j 个字符串的最长子序列 与 前 j-1 个字符串与前 i 个字符串的最长子序列，选取长度更长的一种情况。

dp[ i ][ j ] = max{  dp[ i ][ i-1 ] , dp[ i-1 ][ i ]  };

得到公共子序列，从右下角开始依次挑选相等的。但得到的公共子序列可能不唯一。