動的計画法#

読み: どうてきけいかくほう
英名: Dynamic Programming

動的計画法は応用数学者 Richard E. Bellman によって初めて使われた言葉であり，最適性原理を持つ多段階決定過程に対して適用できる特別なアルゴリズムである．全般的にツリーで表現される全探索問題に対する手法で，指数的に爆発する探索ツリーを多項式時間の問題に置き換えるものなど，劇的に探索範囲を小さくするという特徴がある．基本的に計算機で解くことを前提としたアルゴリズムで，実装する場合には再帰構造を持ちメモリを潤沢に使ったものになることが多い．