1D最長増加サブシーケンスの再帰的解法でのメモ化

Question

配列内のLIS（Longest Increasing Subsequence）の計算は、非常に有名な動的プログラミング問題です。しかし、すべてのチュートリアルでは、最初にDPの概念を使用せずに再帰的解を示し、Bottom-Up DP（反復解）を適用して解く。

私の質問は：

がどのように我々は再帰ソリューション自体にメモ化を使用します。 Memoizationだけでなく、1Dアレイを使用してメモを作成する。

私はいくつかの調査を行いましたが、関連性は見つかりませんでした。再帰的メモ帳が尋ねられた場所は2つありますが、1 & 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 トップダウンソリューションはボトムアップおよびその逆に再フレーミングすることができることを読んだので、私は解決策を知って好奇心旺盛です。

誰かが同じことについて洞察を与えることができれば、非常に役に立ちます。

ありがとうございます。

Answer 1

問題は根本的に解決するためには2Dデータ構造が必要であるため、これはできません。

ボトムアップアプローチは、データ構造の一度に1つの行を生成することによって不正行為を行うことができます。時間をかけて見ると、2Dデータ構造が生成されますが、常にその次元が1つしか表示されません。

トップダウンアプローチでは、2Dデータ構造全体を構築する必要があります。

これはDPの基本的なトレードオフです。通常、トップダウンアプローチを書き留めるほうが簡単です。しかし、ボトムアップ・アプローチは、いつでも全体のデータ構造の一部を持たなければならず、したがって、メモリ要件が大幅に低くなります。