最长递增子序列错误答案

Question

我为最长的递增子序列编写了一个递归解决方案，它运行得非常好。但是当我在相同的代码上应用 dp 时，它给出了不同的答案。问题 Link：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 (编[]) 递归代码给出 4 个答案（正确）但是 DP 代码给出了 3 个答案（不正确）

Answer 1

您的代码有 2 个问题：

错误 1

首先在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

错误 2

你的函数LISdp中的第二个，在我看来不需要语句

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

您应该只删除这个（上面的）语句，程序会产生预期的输出 4，如 here 所示。基本上你没有想过这个（LISdp 的工作）。您可以使用调试器 来查看哪里出错了。

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

Answer 2

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

用“在递归前包含当前元素”解决递归再次”与“在再次递归之前不包括当前元素”相比。这正是您对递归解决方案所做的。
采用步骤 1 的递归解决方案，并添加先前计算结果的缓存，以避免重复递归。缓存，可以概念化为一个多维矩阵，它将传递给递归函数的所有非常量变量参数映射到最终结果。

在您的例子中，每个递归步骤都有两个变量，currIndex 和 maxVal。 a 和 n 实际上在整个递归过程中都是常量。 递归步骤的非常量参数的数量是缓存中的维数。所以你需要一个二维的table。我们可以使用一个大的二维 int 数组，但这会占用大量内存。我们可以用一对嵌套的散列 tables.

来达到同样的效率

您的主要错误是您的缓存只有一维 - 缓存与 currIndex 相比的结果，而不考虑 maxVal 的值。另一个错误是使用向量而不是哈希 table。您拥有的矢量技术有效，但无法扩展。当我们添加第二个维度时，内存使用的规模更糟。

因此，让我们将缓存类型定义为 unordered_map（散列 table），它将 currIndex 映射到另一个散列 table，将 maxVal 映射到递归的结果。您也可以使用元组，但 geeksforgeeks 编码站点似乎不喜欢那样。不用麻烦，我们可以这样定义：

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

那么您的 DP 解决方案实际上只是在递归函数顶部的 CACHE 中插入查找，并在函数底部的 CACHE 中插入。

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;

}

然后使用要解决的输入集的初始调用有效地将 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++ class 的成员变量，这样它们就没有递归的每一步都被压入栈中。缓存通过引用传递，所以没什么大不了的。

最长递增子序列错误答案

longest increasing subsequence wrong answer

c++

recursion

dynamic-programming

错误 1

错误 2