蝙蝠侠的难题解析是怎样的？

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

没 事 找 事

「我的做题历程」：

step1：观察题面。
  「蝙蝠侠需要找到一个最长的字符串，使得这个字符串作为一个子序列被包含在所有的三个字符串中」，可以得出这是一道最长公共子序列，而且有三个字符串。（题型：线性 dp —— 最长公共子序列）
  「蝙蝠侠现在需要找到的是最大的长度，而不是序列」，说明只是一道普通的 LCS。

step2：思考解法。
  第一步思考 dp 状态：

\(dp_{i,j,k}\)：第一串前 \(i\) 项，第二串前 \(j\) 项，第三串前 \(k\) 项中的最长公共子序列长度。

  对于当前的 \(a_{i}, b_{j}, c_{k}\) 而言，只有能做贡献或无法做贡献两种状态。
  若 \(a_{i}= b_{j}= c_{k}\)，则它们能做贡献，此时的最长公共子序列的长度为第一串前 \(i - 1\) 项，第二串前 \(j - 1\) 项，第三串前 \(k - 1\) 项中的最长公共子序列的长度加 \(1\)。
  否则它们无法做贡献，此时放弃做贡献最小的那一项。

  第二步思考状态转移方程：
  本题比常规的 LCS 要多一个字符串，因此只需要再多一维就好。