最长公共子序列图解、算法实现和复杂度分析

LCS和莱文斯坦距离的解决思路非常类似，都是利用动态规划的方式来解决。可以参见上一篇“莱文斯坦距离”，两个概念对比着看理解为更深入！ LCS定义同样引用百科：最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。与查找最长公共子串的问题不同的地方是：