题目：求两字符串的最长公共子序列的长度。

 

题外话：最长公共子串，子序列问题是被充分讨论的问题，网上一搜一大把，请bing之。

本题只要求求最长公共子序列的长度，而不需要记录最长的公共子序列，给予了我们便利，请参考代码：

1 int max(int a, int b) 2 { 3     return a > b ? a : b; 4 } 5  6 int lcs(char* str1, char* str2) 7 { 8     if (str1 == nullptr || str2 == nullptr) 9     {10         return -1;11     }12 13     if (*str1 == '\0' || *str2 == '\0')14     {15         return 0;16     }17 18     if (*str1 == *str2)19     {20         return 1 + lcs(str1 + 1, str2 + 1);21     }22 23     return max(lcs(str1 + 1, str2), lcs(str1, str2 + 1));24 }

 

其基本思想就是：

LCS(S,T)，则有如下情况：

1.S[m] = T[n]，那么LCS(Sm,Tn) = LCS(Sm-1,Yn-1) + 1

2.当S[m] != T[n] ，那么LCS(Sm,Tn) 便是  LCS(Sm,Tn-1)和LCS(Sm-1,Tn)中较大者。