最適性原理

動的計画法は、最適性原理と多段階決定過程の２つの用語で説明されることが多い。

で、最適性原理はざっくり言うと

問題全体で最適解を作るのなら、部分問題も全て最適解じゃないといけないよね

みたいなやつ（厳密性に欠けます）。複数言い換えると

フルコンボするなら、途中で切り取ったときもフルコンボしてる必要があるよね

家から学校へ行く最短経路の途中にコンビニがあるとき、その最短経路は家からコンビニに行く最短経路と重なってるよね

まあつまり、「どこで切り取っても最適解になってる」みたいなやつです。