動的計画法：あなたの思っていることではない

アルゴリズムの学習において「動的計画法」という用語は、しばしば混乱を招きます。「動的」とは、その変化性を指すのではなく、「計画」というプログラミングの意味を指します。これは、1950年代にエンジニアが建設プロジェクトを「プロセススケジューリング」として計画したことに由来します。コンピュータサイエンスにおいて、動的計画法とは、問題を解決するために必要なサブステップの順序を計画することです。例えば、フィボナッチ数列を計算する場合、「プログラム」とは、依存関係の順序でfib(2)からfib(10)を計算するステップのシーケンスです。これはトップダウンまたはボトムアップで計画できます。最終的な計画は同じであり、どちらも動的計画法と見なされます。リチャード・ベルマンは、国防長官の「数学研究」への嫌悪感を避けるために、この用語を作り出し、「動的」という形容詞は軽蔑的に使えないため、「動的計画法」という語を選んだのです。