動的計画法

概要

動的計画法(Dynamic Programming)とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていくアルゴリズムの総称です。

(引用:Wikipedia)

競プロでは組み合わせ数の数え上げ等によく使われます。

私の雑な理解としては、「現状態でのパターン数から次状態のパターン数を算出する」といった感じでしょうか。

関連問題