最长递增子序列错误答案

Question

我为最长的递增子序列编写了一个递归解，它运行得非常好。但是当我在同一个代码上应用dp时，它给出了不同的答案。问题链接：https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence-1587115620/1递归代码：

int LISrecursive(int arr[], int n, int currIndex, int maxVal) {
    if (currIndex == n) {
        return 0;
    }
    int included = 0, notIncluded = 0;
    if (arr[currIndex] > maxVal) {
        included = 1 + LISrecursive(arr, n, currIndex + 1, arr[currIndex]);
    }
    notIncluded = LISrecursive(arr, n, currIndex + 1, maxVal);

    return max(notIncluded, included);

}

DP代码：

int LISdp(int arr[], int n, int currIndex, int maxVal, vector<int> &dp) {
    if (currIndex == n) {
        return 0;
    }
    if (dp[currIndex] != -1) return dp[currIndex];
    int included = 0, notIncluded = 0;
    if (arr[currIndex] > maxVal) {
        included = 1 + LISdp(arr, n, currIndex + 1, arr[currIndex], dp);
    }
    notIncluded = LISdp(arr, n, currIndex + 1, maxVal, dp);

    return dp[currIndex] = max(notIncluded, included);

}

int32_t main() {
    int n;
    cin >> n;
    int arr[n];
    vector<int> dp(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << LISrecursive(arr,n,0,-1); 
    cout << LISdp(arr, n, 0 , -1, dp);
    return 0;
}

我不知道我做错了什么？对于这个测试用例6（n）6 3 7 4 6 9（arr[]），递归代码给出了4个答案（正确），而DP代码给出了3个答案（不正确）

Answer 1

您的代码中有2个问题：

首先，在C语言中，数组的大小必须是编译时常数。因此，以以下代码段为例：

int n = 10;
int arr[n]; //INCORRECT because n is not a constant expression

正确的写法应该是：

const int n = 10;
int arr[n]; //CORRECT

同样，以下内容（您在代码示例中所做的）也不正确：

 int n;
 cin >> n;
 int arr[n];// INCORRECT because n is not a constant expression

其次，在函数LISdp中，在我看来，似乎不需要该语句

if (dp[currIndex] != -1) return dp[currIndex];//no need for this statement

您只需删除这个（上面的）语句，程序就会产生预期的输出，如图所示。基本上，您还没有想过这一点（LISdp正在工作）。您可以使用调试器查看哪里出错。

您的代码中可能还有其他问题，但到目前为止，我能够发现这2个问题。

Answer 2

当我想到动态编程时，我通常将其分解为两个步骤：

>

与“在再次递归之前不包括当前元素”相比，使用“在再次递归之前包括当前元素”求解递归。这正是您使用递归解决方案所做的。

采用步骤1中的递归解，并添加先前计算结果的缓存，以避免重复递归。缓存可以概念化为多维矩阵，将传递给递归函数的所有非常量变量参数映射到最终结果。

在您的例子中，每个递归步骤都有两个变量，currIndex和maxVal。a和n实际上是整个递归过程中的常量。递归步骤的非常量参数的数量是缓存中的维数。所以您需要一个二维表。我们可以使用一个大的2-d int数组，但这会占用大量内存。我们可以使用一对嵌套的哈希表来实现相同的效率。

您的主要错误是您的缓存只有一维——与currIndex相比缓存结果，而不管maxVal的值。另一个错误是使用向量而不是哈希表。您拥有的向量技术有效，但不能缩放。当我们添加第二个维度时，内存使用方面的缩放甚至更糟。

因此，我们将缓存类型定义为一个无序的_映射（哈希表），它将currendex映射到另一个哈希表，该哈希表将maxVal映射到递归结果。你也可以使用元组，但Geeksforgeks编码网站似乎不喜欢这样。不用麻烦，我们可以定义一下：

typedef std::unordered_map<int, std::unordered_map<int, int>> CACHE;

然后，DP解决方案实际上只是将查找插入递归函数顶部的缓存中，并将其插入函数底部的缓存中。

int LISdp(int arr[], int n, int currIndex, int maxVal, CACHE& cache) {
    if (currIndex == n) {
        return 0;
    }

    // check our cache if we've already solved for currIndex and maxVal together
    auto itor1 = cache.find(currIndex);
    if (itor1 != cache.end())
    {
        // itor1->second is a reference to cache[currIndex]
        auto itor2 = itor1->second.find(maxVal);
        if (itor2 != itor1->second.end())
        {
            // itor2->second is a reference to cache[n][maxVal];
            return itor2->second;
        }
    }

    int included = 0, notIncluded = 0;
    if (arr[currIndex] > maxVal) {
        included = 1 + LISdp(arr, n, currIndex + 1, arr[currIndex], cache);
    }
    notIncluded = LISdp(arr, n, currIndex + 1, maxVal, cache);

    // cache the final result into the 2-d map before returning
    int finalresult = std::max(notIncluded, included);
    cache[currIndex][maxVal] = finalresult; // cache the result
    return finalresult;

}

然后使用要求解for的输入集的初始调用有效地将INT_MIN传递为初始maxVal和一个空缓存：

int N = 16
int A[N]={0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};

CACHE cache;
int result = LISdp(A, N, 0, INT_MIN, cache);

一个较小的优化是将A、n和cache作为封装解决方案的C类的成员变量，这样就不必在递归的每个步骤中将它们推到堆栈上。缓存是通过引用传递的，所以这没什么大不了的。