algorithm - 寻找所有可能的最长递增子序列

Question

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

例如:给定的字符串是qapbso

这里最长递增子序列的长度是 3。我想找到所有可能的长度为 3 的最长子序列。即“abs”、“aps”、“abo”。

我正在使用动态规划，但我只得到一个 LIS。我想列出所有这些。

Answer 1

因此典型的 DP 解决方案将生成一个数组，其中您知道从给定位置开始的最长可能子序列是什么我假设您有一个长度为 n 的数组，其中 dp[i] 存储长度以索引为 i 的元素开始的最长非递减子序列。

现在打印所有 LNDSS(最长非递减子序列)最容易使用递归完成。首先通过选择 dp 中的最大值来找到 LNDSS 的实际长度。接下来从 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 个，但可以增加。该解决方案没有最好的设计，但我专注于使其简单而不是精心设计。

希望这对您有所帮助。