ノート:動的計画法

定義

動的計画法の定義はだいぶ曖昧かつ時代と共に少しずつ変わっている気がするのですが、少なくとも「表に埋める」「メモリに記録する」というのは定義に書いてはまずいです。最近のプログラミング言語のいくつかは関数のメモ化をサポートする機能があるため、表を使わなくても、計算結果を記録する手段があります。本質は「表を埋める」事ではなく、計算結果を記録することです。また、メモリではなく、ストレージに保存しても良いので、メモリというのを定義に加えるのもＮＧです。（もちろん、ほとんどのケースでメモリに保存します）。定義としてはメモ化再帰を動的計画法に含めたくない流派がいるみたいなのですが、再帰はスタック＋ループに置き換え可能であり、アルゴリズム論としては、「再帰＋メモ化」と「ループ＋メモ化」の違いは本質的ではなく、アルゴリズムイントロダクションなどに記載されているように、メモ化再帰は動的計画法に含めるべきです。また、再帰を動的計画法の定義に加えるのはＮＧですが、メモ化再帰は再帰というのが言葉に含まれているので再帰が必須です。--MoreNet（会話） 2014年3月9日 (日) 15:10 (UTC)

動的計画法を利用したプログラム（トップダウン方式）

フィボナッチ数を計算する手法のうち「再帰＋メモ化」についてSSスキーナは「アルゴリズム設計マニュアル（上）」にて「キャッシングによるフィボナッチ数」という項目で解説しており、「再帰呼び出しの結果をキャッシングすることは、ほとんど動的計画法のようなものである。もし君が、より微妙な考察より余分なプログラミングをするのを好むならここで止めてもよい。」と記述しています。「再帰＋メモ化」と動的計画法は微妙な何かが異なることになります。また、「ループ＋メモ化」についてはスキーナの同書ではフィボナッチに関して配列を使わない方法も説明しています。微妙な点とは再帰式を計算可能な方向で順次適用し最終結果を得ることであり、途中の計算結果を全て記憶する必要はフィボナッチに関してはありません。このような内容について本文に注釈が必要と思われます。 --Yasushi sapporo（会話） 2019年5月17日 (金) 02:56 (UTC)