end0tknr's kipple - web写経開発

太宰府天満宮の狛犬って、妙にカワイイ

動的計画法 - Dynamic Programming

「細かくアルゴリズムが定義されているわけではない」がポイント

定義 - wikipedia より

細かくアルゴリズムが定義されているわけではなく、
下記2条件を満たすアルゴリズムの総称。

帰納的な関係の利用:
  より小さな問題例の解や計算結果を帰納的な関係を
  利用してより大きな問題例を解くのに使用する。
計算結果の記録:
  小さな問題例、計算結果から記録し、
  同じ計算を何度も行うことを避ける。
  帰納的な関係での参照を効率よく行うために、
  計算結果は整数、文字やその組みなどを見出しにして管理される。

参考url

以下のurlが分かりやすいと思います。

https://www.momoyama-usagi.com/entry/info-algo-dp