重複の可能性あり:。 動的計画法とメモ化:トップダウンとボトムアップのアプローチ
この件に関する記事をたくさん見てきましたが、どうも納得がいきません。あるときは再帰と動的プログラミングが同じに見え、またあるときはメモ化と動的プログラミングが同じに見えます。どなたか、何が違うのか説明していただけませんか?
P.S. また、同じ問題で3つのアプローチを使ったコードを紹介してもらえると助かります。(例えば、フィボナッチ級数の問題では、私が読んだすべての記事が再帰を使用していたと思いますが、ダイナミックプログラミングと呼ばれていました。)
再帰+メモ書き」は、まさに「動的計画法」の一種であり、「トップダウン」アプローチによる動的計画法です。
より正確には、特に「再帰」を使う必要はない。分割統治とメモ化の組み合わせはトップダウンの動的計画法である。(再帰はLIFOの分割統治であり、FIFOの分割統治や他の種類の分割統治を使うこともできる)。
したがって、次のように言うのがより正しい。
divide & conquer + memoization == top-down dynamic programming
また、非常に形式的な見方をすれば、反復的な部分解を生成しない問題(つまり、メモ化のメリットがない)に対して、分割統治解を実装すれば、この分割統治解は動的計画法の退化例であると主張することができるのです。
しかし、動的計画法*はより一般的な概念です。動的計画法ではボトムアップ的なアプローチが可能であり、分割統治+メモ化とは異なる。
詳しい定義はネットで調べればわかると思います。ここでは、物事を単純化するための私の試みです。
再帰は再び自分自身を呼び出している。
動的計画法とは、特定の構造(最適部分構造)を持つ問題を解く方法であり、問題は、元の問題に類似した部分問題に分解することができる。明らかに、DPを解くために再帰を呼び出すことは可能である。しかし、再帰は必要ない。再帰を使わなくても、DPは解ける。
メモ化は、再帰に依存するDPアルゴリズムを最適化する方法である。ポイントは、すでに解かれた問題をもう一度解くことではありません。サブ問題の解のキャッシュとみなすことができる。
再帰は、メモ化や動的計画法とは全く関係がなく、全く別の概念である。
そうでなければ、これは、https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches の重複した質問です。