最长公共子序列
最长公共子序列（Longest Common Subsequence, LCS）是动态规划的经典问题。
问题描述
不要求连续，不要求位置相同，考虑次序。即从序列一中选出若干元素，从序列二中选出等量元素，保持原有次序完全一致则是公共子序列。
暴力搜索局限
需要枚举 X 的所有子序列，并一一确定是否为 Y 的子序列，需要进行 2ⁿ 次比较。
优化解结构
引入第 i 前缀的概念（原序列前 i 个元素组成的序列）。
核心规律：
- 如果两个序列的最后一个元素相同，则该元素一定在公共子序列中
- 如果不相同，则公共子序列要么是去掉第一个序列最后一个元素的问题，要么是去掉第二个序列最后一个元素的问题
代价转移方程
算法实现
B 数组充当路径指引作用，按照 B 的指引从上到下构建出最优化解。
算法分析
时间复杂度 O(mn)，空间复杂度 O(mn)。
链接到
- 上一个知识点：2.2 矩阵链乘法
- 下一个知识点：2.4 最优二叉搜索树