给出一个多项式时间算法，该算法以三个字符串 A、B 和 C 作为输入，并返回作为 A、B 和 C 的子序列的最长序列 S。
最佳答案
让 dp[i, j, k] = longest common subsequence of prefixes 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) 。关于algorithm - 找到是 A,B,C 字符串的子序列的最长序列 S，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4705276/