[LintCode]Longest Common Subsequence

经典的DP问题，解法也可以扩展到很多其他的题目。假设输入字符串为s1和s2，我们用DP[i][j]表示s1中前i个字符和s2中前j个字符的LCS，我们有递推公式：

• DP[i][j] = DP[i - 1][j - 1] + 1, if s1[i] == s2[j]
• else, DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])

假设输入串长度分别为n和m，时间和空间复杂度均为O(m * n)，代码如下：

和Longest Common Substring类似，我们可以用滚动数组进行优化，空间可以优化到O(n)，代码入下：