给出一个多项式时间算法，采用三根弦，A，B和C，作为输入，并返回最长的序列S是一个序列A，B和C。

Give a polynomial time algorithm that takes three strings, A, B and C, as input, and returns the longest sequence S that is a subsequence of A, B, and C.

推荐答案

让 DP [I，J，K] = $ P $的最长公共子pfixes A [1..i]，B [1..j]，C [1..k]

我们有：

dp[i, j, k] = dp[i - 1, j - 1, k - 1] + 1 if A[i] = B[j] = C[k]
              max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

类似于2d的情况下，除有3个维度。复杂性是 O（LEN A * LEN B * LEN C）。