动态规划深入分析——LCS问题

最长公共子序列

• 问题剖析
  • • 探讨最优解的结构属性
    • 构建最优值的递推表达式
    • 采用自底向上的方式计算最优值，同时记录对应的最优数值与策略方案
    • 组装最优解

  • 算法构思

  • 精准图示解析

  • 伪代码详述

  • 完整源码实现

  • 相关题目解答

问题分析

针对两个序列X={x1,x2,…,xm}与Y={y1,y2,…,yn}，目标是确定其共同拥有的最长子序列。
上述内容的阐述参考了《趣学算法》一书，该书的具体位置可于Dijkstra的文章末中查阅。

分析最优解的结构特征

假设已知 Zk={z1,z2,…,zk} 是 X={x1,x2,…,xm} 与 Y={y1,y2,…,yn} 的最长公共子序列，那么可以将其划分为三种情形进行分析。
当 Xm 等于 Yn 且同时等于 Zk 时，则 Zk-1={z1,z2,…,zk-1} 即为 Xm-1 与 Yn-1 的最长公共子序列。
若 Xm 不等于 Yn，且 Xm 也不等于 Zk，此时可将 Xm 从序列中剔除，则 Zk 将成为 Xm-1 与 Yn 的最长公共子序列。
若 Yn 不等于 Xm，且 Yn 同样不等于 Zk，则按照上述逻辑处理，Zk 应为 Xm 与 Yn-1 的最长公共子序列。

建