algorithm - 最長増加部分列の再帰的解法における 1D メモ化

Question

配列内の LIS (最長増加部分列) の計算は、非常に有名な動的計画法の問題です。ただし、すべてのチュートリアルでは、最初に DP の概念を使用せずに再帰的なソリューションを示し、次にボトムアップ DP (反復ソリューション) を適用して解決します。

私の質問は：

再帰的なソリューション自体で メモ化をどのように使用しますか。ただのメモ化ではなく、一次元配列を使ったメモ化。

いくつかの調査を行いましたが、関連するものは何も見つかりませんでした。再帰的なメモ化について質問された箇所は1 & 2の2 箇所ありますが、そちらの解決策はメモ化に 2D Map / Array を使用しています。

とにかく、1D配列でソリューションをメモすると、間違った出力が得られます。これが私がしたことです：

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;
}

このソリューションが間違った出力を与える理由はわかっていますが、次のようになります。

以前の値に基づいて、与えられたインデックスに対して複数のソリューションが存在する可能性があります。

しかし、1D配列を使用してそれを行う方法を知りたいです。

すべての DPのトップダウンソリューションをボトムアップに、またはその逆に再構成できることを読んだので、ソリューションを知りたいと思っています。

誰かが同じことについて何らかの洞察を提供できれば、非常に役に立ちます。

前もって感謝します。