如何将最长公共子序列（LCS）的递归和动态规划一致性改写为长尾关键词？

本文共计3536个文字，预计阅读时间需要15分钟。

1. 前言 + 动态规划处理字符相关案例中，求最长公共子序列及求最短编辑距离，是经典中的经典案例。+ 讲解此类问题的算法在网络上应用广泛，例如便如同此类，不乏有详细阐述的资料。

1. 前言

动态规划处理字符相关案例中，求最长公共子序列以及求最短编辑距离，算是经典中的经典案例。

讲解此类问题的算法在网上一抓应用一大把，即便如此，还是忍不住有写此文的想法。毕竟理解、看懂都不算是真正掌握，唯有瞧出其中玄机，能有自己独有的见解和不一样的感悟方算是把知识学到灵魂深入。

好了！闲话少说，进入正题。

2. 最长公共子序列(LCS)

2.1 问题描述

最长公共子序列，指找出 2 个或多个字符串中的最长公共子序列。

如字符串 s1=kabc和s2=taijc，其最长公共子序列是ac。

Tips： 子序列只要求其中字符保持和原字符串中一样的顺序，而不一定连续。

2.2 递归思想

这是一道求最值的题目，只要是求最值，必然会存在多个选择，原理很简单，如果没有多个选择，还有必要纠结谁是最大谁是最小吗？

Tips： 在你面前有苹果、桔子、香蕉……你只能选择一个，这时候方有纠结。如果面前只有苹果，还会纠结吗？

面对此问题，可以采用化整为零的思想，从宏观层面转移到微观层面，缩小问题的规模的递归思想。