動的計画法（Dynamic Programming, DP）は、ある状態における求めたい値を一度計算して記録し、それを再利用することで効率的に答えを求める手法です。特に状態間の遷移に着目し、遷移式を立式できる場合に非常に効果的となります。ここでいきなり状態、遷移と出てきて混乱されるかもしれません。これらの単語が何を指しているのかを文章だけで理解するのは難しいため、実際に例題や具体例を見ていって理解していきましょう。
DPにおいて筆者は状態という単語を使用していますが、普遍的に通じる意味を持つものではないです。ある状況や条件における答えを求めるというのがDPでの主なやりたいことです。この状況や条件を指すものとして状態(state)という単語が筆者はしっくりくるかと思って使用しています。
形式言語などでオートマトンを扱ったことがある方は状態機械(state machine)の状態(state)と同じ様なイメージを持っていただけると分かりやすいかと思います。
