ニコニコ大百科

パスカルの三角形は、
nCr=n-1Cr-1+nCr
→ nCr=n-1Cr-1+n-1Cr
^^^
ではないでしょうか．

^^^がずれました．
n-1Cr の n-1の下に書いたつもりです．

>>2
御指摘ありがとうございます。修正いたしました。

08年初頭だったかな「巡回セールスマン問題」というタグを
無差別につけて回っているヤツがいたようだけど
暇だったから全部辿って消してやった

自分に意味がわからなかったから勝手に意味を変える編集者スゲー
最適解はどこへ行った

ここの定義だと単に漸化式とか再帰的アルゴリズムのことを言ってるだけだよな。

必須定義:
* 問題全体は部分部分の結果を足せば出る
* 一度解いた問題は二度解かない <- これ重要
** 単に割ってくだけの作りだと同じサブ問題があちこちに出てダブることがあるので、その時は前の結果を使いまわす

必須ではないけどデフォ:
* そうやってベストケースな組み合わせを効率良く探す

そもそも動的「計画法」という名前は、最終結果はとりあえず置いといて、先にどんな材料があれば答えが出るか決めちゃおうというところから来てる。
一般的にでかい問題は分割統治して、それぞれ別に作った結果を最後にがっちゃんこするってのがよくあるセオリーなわけだが、それぞれが完全に独立でやっちゃうと部品の共通化ができなくてすげー効率が悪いわけよ。だから元締め側でそこは管理して「これは余所で用意したのと一緒だからそれを使いまわす」という風に車輪の再発明をしないというのがミソなわけだ。
ただ普通の計画と違って部品を作りながら足りないところを増やしていくから動的だという言い方をする。

>>7
なるほどわかりやすい（ありがとう！）