小编Shi*_*sal的帖子

计算数组中的 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 …