動的プログラミングの「プログラミング」は、線形プログラミングや整数プログラミング、制約プログラミングの「プログラミング」と同じように考えた方がいいよ。実際、素人の言葉で言っても、テレビ番組のプログラミングのように考える方が、コンピュータプログラミングに関連していると考えるよりも正確だよね（TFAでも言われてるけど）。

ステップの順序はダイナミックプログラミングの結果なんだ。すべてのステップの順序がダイナミックプログラムというわけではないよ。そして（私が主張するには）核心的な結果はかなり数学的で、メモ化や再帰は登場しないけど、偏微分方程式は出てくるよ。ハミルトン・ヤコビ・ベルマン方程式をチェックしてみて。

「メモ化＋再帰」を「ダイナミックプログラミング」に昇格させるのは、ベルマンが予想していなかった展開のようですね。 まあ、実際にはそんな展開は起こってないけど。ダイナミックプログラミングは、常にメモ化を使った再帰として実装できます。でも、再帰的でメモ化されたアルゴリズムが必ずしもダイナミックプログラミングの例になるわけではないです。ダイナミックプログラミングのポイントは、再帰呼び出しがキャッシュにヒットするように再帰を設定することです。キャッシュがあって、運が良ければヒットするってわけじゃないんです。

私も同じ経験をしたよ：私のメンターたちも「動的プログラミング」が何か知らなかったし、我が国の競技（IOIにインスパイアされた問題を作った）では5問中2問が動的プログラミングを必要としたんだ。当然、初めては失敗した（2004年）。その後、動的プログラミングが何かを学んで、次の年（2005年）には成功したよ。

1997年のケープタウンでのIOIのホスティングチームに参加してたんだけど、君が言ってたような参加者との会話をしたり、ダイナミックプログラミングについても学んだよ。君の「再帰 + 結果を保存する、時には反復的にできる」という説明が一番の要約だね。いい例としては、反復的なフィボナッチアルゴリズムがあるよ。あの時の面白いエピソードとして、参加者のマシンにシリアルポート経由で接続するスコアリングプログラムには特別な注意が必要だったんだ。前の年に、一人の参加者がシリアルポートのインターフェースをハッキングして結果を操作してたからね。 :-)

プログラミングコンテストで「軍拡競争」みたいなことがあったのかな？ 知識が広がって、より難しい問題を選ぶ必要が出てきてるよね。最近ではダイナミックプログラミングはICPCタイプの問題の基本的な要素になってるし。

あなたの素晴らしいストーリー、めっちゃ好きです！私のは普通の話ですけど。卒業してからプログラミングを始めたんですが、ダイナミックプログラミングはスタンフォードのアルゴリズムのコースを見てやっと理解できました（MOOCに感謝！）。でも正直言って、実際に役立つことはあまりしてないです。普通の物事に新しい視点を与えてくれたくらいかな。例えば、太極図には大きな知恵があるかもしれないって気づきました（ここに画像があります: https://commons.wikimedia.org/wiki/File:Yin_yang.svg）。今の問題を分けて、下のレベルで解決できるんです（陰陽の点みたいに）。もちろん、その下のレベルにもさらに分割や計算があって、最後には何も残らなくなるまで続きます。一方で、基礎から始めて上に構築していく（ボトムアップ）こともできて、高レベルの計算に向かって進むことができます。そこでまた分割が待っていて、最終的には一つの大きな統一された答えが出てくるんです。実際の使い道としてはあまり役に立たないですよね？^^

IOI 2001の記憶を整理できるかな？初日の結果が遅れたんですが、参加者が問題の一つで検索をコンパイル時のC++テンプレートメタプログラムにエンコードしたからだと思います。二日目には、解答にもコンパイル時の制限があったような気がします。もっと詳しいこと覚えてますか？

ずっと不思議に思ってたことがあるんだけど、ダイナミックプログラミングが普通のプログラミングより「ダイナミック」ってどういうことなんだろう？ 再帰は「静的」だけど、結果を保存すると「ダイナミック」になるのはなんで？

あ、それ私が行った年だ。懐かしい思い出。全然準備が足りなかったな。モバイルフォンのセルサマレーション問題で、自分がどれだけ知らないかを痛感したし、その後どれだけ学ばなきゃいけないかもわかった。それがこの分野への愛を深めたんだ。経験が本当に楽しかった。

アメリカ生まれの英語ネイティブとして、あのフレーズにはいつも苦労してた。結局、実際の問題セットに価値を与えないから、頭の中では誤称だと思うようにしてた。

初めてのプログラミングコンペ（2002年の全国ICPC予選）で、チームメイト（あまり知らない人たちで、急いでチームを作ったばかり）にコンテストの数分前に「ダイナミックプログラミングって何？」って聞いたんだ。そしたら一人が「それは再帰関数の出力をキャッシュするだけだよ」って言ってた（厳密にはメモ化だけど、気にしないで）。締切の数分前にDPを使って問題を解決できて、結果的に3位になってICPCに進めた。楽しい時間だったな。

確かに、これは婉曲表現として使えるし、場合によっては悪口にもなるね。「ダイナミックな真実性」とか「ダイナミックな道徳感」とか。

ダイナミックスコープもあるよ。これはレキシカルスコープ、つまり静的スコープとは対照的だね。ダイナミックタイピングの擁護者はいるけど、ダイナミックスコープは今では間違いだと広く見なされてる。少なくともデフォルトでダイナミックスコープはそうだけど、特別な使い方もあるし、HaskellではReaderモナドがダイナミックスコープとほぼ同型だから、誰も文句言わないよ。

うーん、キャッシュ再帰はちょっと一般的すぎるかな。キャッシュと再帰を使ってできることはほとんど何でもあるよ。数学的最適化の授業では、ダイナミックプログラミングを「グラフの最長経路を見つけるのと同型の問題」と定義してたんだ。ここでの「最大化」や「加算」の「オーバーロード」について説明すると、行列の掛け算は通常は掛け算（×）と加算（+）を使うけど、ミン・プラス代数では、加算を最小値に、掛け算を加算にオーバーロードすると、行列の掛け算がグラフの隣接行列の2つの経路を跳ぶことと同じになるんだ。（ちょっと混乱させてたらごめんね。）具体的には、隣接行列Aを使ってA* := 1 + A + AA + AAA + ...を計算することは、グラフのエッジホッピングの推移閉包を求めることと同じで、すべての頂点のペア間の最短経路になるんだ。もし加算を最大値に、掛け算を加算にオーバーロードすると、最長経路を見つけられるよ。それにはグラフにサイクルがないことが条件だけどね。さて、ダイナミックプログラミングに戻ると、ダイナミックプログラミングの共有最適部分構造特性は、最長経路を見つけるのとまったく同じなんだ。この構造は制約が厳しいように聞こえるかもしれないけど、ダイナミックプログラミングのほとんどの例に適用できることがわかるよ。P.S. ちょっと記憶が曖昧だったから、ChatGPTに助けを求めたら、どうやら完全に間違ってはいなかったみたいだね。https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c1... P.P.S. 上で言ったこととは裏腹に、「キャッシュ再帰」はダイナミックプログラミングよりもまだ良い名前だと思うよ。

実際、メモ化された再帰に過度に焦点を当てると、ダイナミックプログラミングの核心的な概念を損なうと思うんだ。投稿にも書いてあるように、プログラミングという用語は計画のための表形式の方法を指していて、つまり具体的には問題を解決するためのボトムアップ計算を指してるんだ。ここでの強調点は、望ましい結果に到達するための計画を表にまとめる順序があらかじめ決まっていることなんだ。それが広い問題の解決策になる。メモ化された再帰関数は、どの順序で表を作成すべきかという問題を特に回避するデジタルコンピュータ上の実装方法なんだ。私は、再帰的メモ化はダイナミックプログラミング問題（ダイナミックプログラミングの解決策を許容する問題の宇宙として定義される）に対する可能な解法技術だと主張するけど、厳密に言えば、それ自体はダイナミックプログラミングではないよ。

「キャッシュ再帰」は広すぎると思うな。私は「最小メモリメモ化」にすることが多いよ。1) 再帰的な解法は遅すぎることが多いけど、メモリはあまり使わない。2) メモ化された解法は、1のアルゴリズムをかなり速くするけど、メモリ使用量が膨れ上がる。3) ダイナミックプログラミングの解法は、将来の部分解に必要な前の部分解だけをメモリに保持するんだ。だから「最小メモリメモ化された」解法になる。これは、部分解の賢い順序が必要で、最も早くキャッシュを解放できるようにすることが多いよ。君の「キャッシュ再帰」は私には2番目のように聞こえるし、ダイナミックプログラミングの要点は、いつキャッシュからエントリーを削除するかを見極めることなんだ。

ダイナミックは絶対に無意味じゃないですよ。私は最適制御理論の観点からダイナミックプログラミングに詳しいですが、ダイナミカルシステムに焦点を当てています。ダイナミックプログラミングの中心方程式はハミルトン-ヤコビ-ベルマン方程式で、古典力学のハミルトン-ヤコビ方程式の一般化です。この文脈での「プログラミング」という用語は、線形プログラミングや確率的プログラミングにも存在します。今は混乱するかもしれませんが、これらの用語は現代のプログラミングやコンピュータよりも前から使われていたものです。正直、コメント欄でみんなが再帰＋メモ化について話しているのを見てちょっと戸惑っています（効率的に逆帰納法を実装する方法として？）。コンピュータサイエンスはダイナミックプログラミングのアイデアの特定の応用や実装を教えていて、それを全体のものと勘違いしている人が多いのかな？

そうですね。私は気にしないけど、この分野は実際のことについて何も伝えない名前がたくさんありますからね。

わざとわかりにくくしてるんだね。記事によると、説明じゃなくてプロモーションのためなんだって。

リソースは見つからないけど、ベルマンによれば、彼は軍隊が使うような名前にはしたくなかったらしいです。要は、彼の研究を守るためですね。いくつかの選択肢があって、「ダイナミック」は軍隊にとって「クール」な響きだったみたいです。そういう意味では、「プログラミング」の部分はかなり正確だけど、個人的には著者が「コンピュータプログラミング」の意味を理解してない気がします。

線形プログラミングはプログラミングと混同されるけど、線形代数や線形モデルとも混同されることがあるよね。