c++ - 通过演化递归解计算最长递增子序列的数量

我如何通过发展递归解决方案来计算最长的LIS数量，例如[1,3,5,4,7]返回2，其中LIS是1,3,5,7和1,3,4,7，对于[3,3,3,3]，它将是4，其中LIS是3，并且其中有4
我递归地计算LIS如下:(我可以使用备忘录来优化此方法，然后根据各种解决方案进一步进入DP，然后进入细分树，但我想直观地将自己引向它们)

int numberOfLis(vector<int>& nums)
{
    //Set the size of count to the size of num, since there cannot be an LIS greater than the size of nums
    vector<int> count(nums.size(), 0);

    //Get the size of the maximum LIS and update the frequency of how many similar sizes have been encountered in the count array
    int maxcount = LIS(nums, INT32_MIN, 0, count);

    //Return the number of occurances by looking it up in our count.
    return count[maxcount];
}

int LIS(vector<int>& nums, int prev, int index, vector<int>& count)
{
    if (index == nums.size()) return 0;

    int with = 0;
    //Increasing sequence, lets select it.
    if (nums[index] > prev) with = 1 + helper(nums, nums[index], index + 1, count);

    //See if we can do better without the current number
    int without = helper(nums, prev, index + 1, count);

    //Get the maximum seen so far and update the frequency in count array
    int maxcount = max(with, without);
    ++count[maxcount];

    return maxcount;
}

我使用count数组vector<int>(nums.size(), 0)来增加最大值，因为我遇到的是++count[max(with,without)]，其中返回的最大值的count将作为答案。这导致count数组使4计数为1而不是2，这是错误的。我正在寻找一种从这里前进的方法。

更新了:添加了count数组的代码并添加了注释

最佳答案

一个子序列的计数大于一个增量，因为可能会有多个子序列以相同的长度结束。

处理示例数据时，当index为1时，with和without均为3。尽管有两个子序列具有此长度，但count[3]仅增加了一次，并且返回3作为最大长度。在上一个调用中使用它时(当index为0时)，with将为4，而without 3将被使用。即使存在两个长度为4的子序列，count[4]也只会增加1。

您需要更改helper不仅返回最长子序列的长度，还返回具有该长度的子序列的数量。

关于c++ - 通过演化递归解计算最长递增子序列的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47495926/