動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 定義[編集] 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 帰納的な関係の利用:より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 計算結果の記録:小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。 概要[編集] 「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いは
![動的計画法 - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/e7379d14529f780137be504ea6c5558e3dc39974/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F7%2F72%2FMax_paraboloid.svg%2F150px-Max_paraboloid.svg.png)