LCS (最长公共子序列)-得到最佳K解

Question

LCS问题得到两个字符串，并返回它们最长的公共子序列。

例如：

字符串上的LCS：大象和eat是3，因为eat是大象-指数0、6、7或2,6,7的子序列。

另一个例子是：

字符串上的LCS：大象和橄榄是2，因为它们最长的公共子序列是le

问题是，是否有一个算法不仅返回最优解，而且还能返回K个最佳解？

Answer 1

有一个返回所有最优解的算法(我认为这就是您所要求的)。

如在维基百科

使用两个字符串的动态规划算法构造表，然后递归地从结束到开始进行回溯，并增加计算，如果(i，j-1)或(i-1，j)中的任何一个可以是当前路径之前的点，那么这两条路径都会被探索。在最坏的情况下，这会导致指数计算。

在最坏的情况下，这些最优序列可以有一个指数型数！