メモ化と動的プログラミングの違いは何ですか? 質問する

Programming.Guide の関連記事:動的プログラミング vs メモ化 vs 表計算

メモ化と動的プログラミングの違いは何ですか?

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

動的プログラミングは、再帰的な性質の問題を反復的に解決する手法であり、サブ問題の計算が重複する場合に適用できます。

動的プログラミングは、通常、表形式を使用して実装されますが、メモ化を使用して実装することもできます。したがって、どちらももう一方の「サブセット」ではないことがわかります。

妥当なフォローアップの質問は、「表形式化（一般的な動的プログラミング手法）とメモ化の違いは何ですか？」です。

表作成法を使用して動的プログラミング問題を解く場合、問題を「ボトムアップ」で、つまり、通常はn次元の表を埋めることで、まず関連するすべてのサブ問題を解決します。表の結果に基づいて、「トップ」/元の問題の解決策が計算されます。

メモ化を使用して問題を解決する場合、すでに解決されたサブ問題のマップを維持することによってそれを行います。これは、最初に「トップ」問題を解決するという意味で「トップダウン」で行います (通常、サブ問題を解決するために下方向に再帰します)。

良いスライド ここ (リンクは現在無効ですが、スライドはまだ残っています):

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

追加リソース:

• ウィキペディア:メモ化、動的プログラミング
• 関連するSO Q/A:動的プログラミングのためのメモ化または表作成アプローチ