[解決済み】メモライゼーションとダイナミックプログラミングの違いは何ですか？

質問

メモライゼーションとダイナミックプログラミングの違いは何ですか？ダイナミックプログラミングはメモライゼーションのサブセットだと思うのですが。そうなのでしょうか？

どのように解決するのですか？

Programming.Guideの関連記事です。 動的計画法 vs. メモ化 vs. 表計算

メモライゼーションとダイナミックプログラミングの違いは何ですか？

メモ化 とは、以前に計算した結果をキャッシュしておき、同じ計算が再び必要になったときにキャッシュされた結果を返すという最適化手法を表す用語です。

ダイナミックプログラミング は、再帰的な性質を持つ問題を繰り返し解くための手法で、部分問題の計算が重複する場合に適用される。

動的計画法は 通常 は集計を使用して実装されていますが、メモ化を使用して実装することも可能です。このように、どちらも他のものの「サブセット」ではないのです。

合理的なフォローアップの質問です。 集計（ダイナミックプログラミングの代表的な手法）とメモ化の違いは何ですか？

表形式で動的計画法を解くと、"という問題が解けます。 ボトムアップ つまり、関連するすべての小問題を最初に解き、通常は n -次元の表。そのテーブルの結果に基づいて，元の問題の解が計算されます．

問題を解くためにメモ化を使う場合は、すでに解いたサブ問題のマップを管理することで行います。あなたはそれを行う"。 トップダウン というのは、最初にquot;top"の問題を解くという意味です（通常、サブ問題を解くために下に向かって再帰します）。

の良いスライドです。 <ストライク こちら (リンクは切れてしまいましたが、スライドはまだ大丈夫です）。

• すべての部分問題を少なくとも一度は解決しなければならない場合、ボトムアップの動的プログラミング・アルゴリズムは、通常、トップダウンのメモ化アルゴリズムよりも一定の係数で性能が向上する。
  • 再帰のオーバーヘッドがなく、テーブル維持のオーバーヘッドが少ない
  • 動的計画法のアルゴリズムにおけるテーブルアクセスの規則的なパターンを利用することで、必要な時間やスペースをさらに削減できる問題もある
• 部分問題空間内のいくつかの部分問題を全く解く必要がない場合、メモ化解法は確実に必要な部分問題のみを解くことができるという利点がある

追加資料です。

• ウィキペディア メモ化 , ダイナミックプログラミング
• 関連するSOのQ/Aです。 動的計画法のためのメモ化またはタブ化アプローチ