最长递增子序列递归解中的一维记忆

Question

计算数组中的 LIS（最长递增子序列）是一个非常著名的动态规划问题。然而，在每个教程中，他们首先展示了不使用 DP 概念的递归解决方案，然后通过应用自底向上 DP（迭代解决方案）来解决它。

我的问题是：

我们将如何在 递归解决方案本身中使用记忆化。不只是记忆，而是使用一维数组记忆。

我做了一些研究，但找不到任何相关的东西。虽然有 2 个地方要求递归记忆1和 2但那边的解决方案是使用 2D Map / Array 进行记忆。

无论如何，用一维数组记住解决方案，会给出错误的输出。这是我所做的：

int lis(int idx, int prev)
{
    if(idx >= N)
        return 0;

    if(dp[idx])
        return dp[idx];

    int best_ans = lis(idx+1, prev);

    int cur_ans = 0;
    if(arr[idx] > prev)
    {
        cur_ans = 1 + lis(idx+1, arr[idx]);
    }
    int ans = max(best_ans, cur_ans);
    dp[idx] = ans;
    return ans;
}

int main()
{
    // Scan N 
    // Scan arr

    ans = lis(0, -1));
    print ans;
}

虽然我知道这个解决方案给出错误输出的原因是：

根据先前的值，给定索引可以有多个解决方案。

但我仍然想知道如何使用一维数组来完成。

我很想知道该解决方案，因为我读过每个 DP自上而下的解决方案都可以重新构建为自下而上，反之亦然。

如果有人可以为此提供一些见解，那将非常有帮助。

提前致谢。

Answer 1

这是无法做到的，因为问题从根本上需要一个二维数据结构来解决。

自底向上的方法可以通过一次生成一行数据结构来作弊。随着时间的推移，它会产生一个二维数据结构，但在任何给定时间你只能看到它的一个维度。

自顶向下的方法必须构建整个二维数据结构。

这是 DP 中的基本权衡。写下自上而下的方法通常更容易。但是自下而上的方法在任何时候都只需要拥有整体数据结构的一部分，因此内存需求显着降低。