问题描述

  1. 求解给定两个字符串的最长公共子序列的长度
  2. 输入：X = { a, b, c, b, d, a, b }，Y = { b, d, c, a, b, a }
  3. 输出：4
  4. 解释：
  5.     { b, c, b, a }是他们的最长公共子序列

解题

计算 最长公共子序列 - 图1 的最长公共子串，设最长公共子串为 最长公共子序列 - 图2

  1. 如果有 最长公共子序列 - 图3，那么最长公共子序列 - 图4，那么最长公共子序列 - 图5，其中最长公共子序列 - 图6是 最长公共子序列 - 图7和最长公共子序列 - 图8的最长公共子串。
  2. 如果 最长公共子序列 - 图9：
    1. 如果最长公共子序列 - 图10，那么最长公共子序列 - 图11和最长公共子序列 - 图12的最长公共子串等于最长公共子序列 - 图13和最长公共子序列 - 图14的最长公共子串
    2. 如果最长公共子序列 - 图15，那么最长公共子序列 - 图16和最长公共子序列 - 图17的最长公共子串等于最长公共子序列 - 图18和最长公共子序列 - 图19的最长公共子串

设 dp[i][j] 表示最长公共子序列 - 图20和 最长公共子序列 - 图21的最长子串长度，则转移方程为：
最长公共子序列 - 图22

注：这里是这样一种转移关系
image.png