找到所有可能的最长增加子序列

Question

我想找到给定字符串中所有可能的最长增加子序列.

例如:给定字符串是 qapbso

这里,最长增加的子序列的长度是3.我想找到长度为3的所有可能最长的子序列.即"abs","aps","abo".

我正在使用动态编程,但我只获得一个LIS.我想列出所有这些.

Answer 1

所以典型的DP解决方案会生成一个数组,在这个数组中你知道从给定位置开始的最长可能的子序列我可以说你有和长度为n的数组,其中dp [i]存储最长的非长度 - 减少以索引为i的元素开头的子查询.

现在打印所有LNDSS(最长的非递减子序列)是最容易使用递归完成的.首先通过选择dp中的greast值来查找LNDSS的实际长度.接下来从dp中的每个元素开始递归,该元素在dp中具有最大值(这些可能多于一个).来自给定索引的递归应该打印从当前索引开始的所有序列,其长度等于值dp [i]:

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

这是c ++中的示例代码(希望它在其他语言中也是可以理解的).我有一个名为stack的全局堆栈,它保留了我们已经添加的元素.它的大小为1000,假设你在LNDSS中永远不会有超过1000个元素,但这可以增加.该解决方案没有最好的设计,但我专注于使其简单而不是精心设计.

希望这可以帮助.