最长公共子序列要求字符在原字符串中必须连续出现

动态规划求解LCS时，状态dp[i][j]表示字符串s1前i个字符与s2前j个字符的最长公共子序列长度，当s1[i-1] == s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；当s1[i-1] != s2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

任意两个字符串的最长公共子序列的长度一定等于两个字符串长度的较小值

动态规划求解LCS的时间复杂度为O(n+m)，其中n和m分别为两个输入字符串的长度