寻找所有可能的最长的递增子序列 [英] Finding All possible Longest Increasing subsequence

问题描述

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

I want to find all possible Longest Increasing Subsequences in a given string.

例如:给定字符串为qapbso

最长递增子序列的长度为3. 我想找到长度3的所有可能的最长子序列.即"abs"，"aps"，"abo".

Here the length of longest increasing subsequence is 3. I want to find all possible longest subsequence of length 3. i.e "abs", "aps", "abo".

我正在使用动态编程，但是我只得到一个LIS.我想列出所有这些人.

I am using Dynamic Programming but I am only getting one LIS. I want to list down all of them.

推荐答案

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

So the typical DP solution to this will produce an array in which you know what is the longest possible subsequence starting at a given position i let's say that you have and array with length n in which dp[i] stores the length of the longest non-decreasing subseq that starts with the element with index i.

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

Now printing all the LNDSS(longest non-decreasing subsequences) is easiest to be done using a recursion. First find the actual length of the LNDSS by seleting the greast value in dp. Next start the recursion from each element in dp that has the maximum value in dp(these may be more then one). The recursion from a given index should print all the sequences starting from the current index that have length equal to the value 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的全局堆栈，该堆栈保留我们已经添加的元素.假设您在LNDSS中的元素数永远不会超过1000，则其大小为1000，但是可以增加.该解决方案没有最好的设计，但我一直致力于使其简单而不是经过精心设计.

This is example code in c++(hope it is understandable in other languages as well). I have a global stack called stack that keeps the elements we have already added. It has size 1000 assuming you will never have more then 1000 elements in the LNDSS but this can be increased. The solution does not have the best possible design, but I have focused on making it simple rather then well designed.

希望这会有所帮助.

这篇关于寻找所有可能的最长的递增子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！