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

Question

计算数组中的LIS（最长增加子序列）是一个非常着名的动态编程问题。然而，在每个教程中，他们首先显示递归解决方案而不使用DP的概念，然后通过应用Bottom-Up DP（迭代解决方案）来解决它。

我的问题是：

我们如何在递归解决方案中使用Memoization。不只是Memoization而是使用1D数组的memoization。

我做了一些研究，但找不到任何相关的东西。虽然有两个地方已经要求递归记忆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 Top-Down解决方案都可以重新定义为Bottom-Up，反之亦然。

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

提前致谢。

Answer 1

这是不可能的，因为问题从根本上需要2D数据结构来解决。

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

自上而下的方法必须构建整个2D数据结构。

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