サブ問題を解決する

Question

ダイナミックプログラミングよりもいつメモを取るのですか？
これらはどちらも同じ時間と空間の複雑さを持っているようです。
親指を優先するのはどういうのでしょうか？

Answer 1

Memoizationは、ダイナミックプログラミングで使用される技術であり、別のエンティティではありません。時間/空間の複雑さはアルゴリズムと実装に依存します。

Dynamic programmingは、通常、ジョブ内の共通のサブタスクを認識する戦略です。サブタスクを複数回実行する代わりに、実行サイクル以外のシステムリソースを使用して、後で使用するために実行結果を取得します。

通常、これは計算結果を格納する単純な問題であり、計算の労力が重複しないようにします。ほとんどの場合、これにはパラメータ値でインデックス付けされた機能結果の格納が含まれます。これはメモです。トップダウンとボトムアップ：より詳細に

...

DPは、2つの基本的な種類があります。ボトムアップの方法は、ベースケースから始まり、要求された結果まで動作します。これは、単純な反復ループと中間結果を格納する配列で実装されることがよくあります。

トップダウン方式はメモです。これにより、元の要求がより小さな問題に壊れ、それぞれの問題が再発します。各サブ問題を解決するので、同じ結果を必要とする他のブランチが使用する結果を格納します。