ALGORITHM NOTE 動的計画法 Dynamic Programming

問題を解く有効な手法の１つが、最終的な解を求めるために、その問題の小さな部分問題の解を用いることです。一般的に小さな問題はより容易に分析・解決できるものです。この手法の代表的なものに、分割統治法（Divide and Conquer)と動的計画法 (Dynamic Programming: DP)があります。 分割統治法では問題を２つ（またはそれ以上）に分け、それらをそれぞれ解き、元の問題を解くためにそれらの分割して解かれた問題を統合して利用する、という処理を再帰的に行います。マージソートが分割統治法のよい例です。 一方動的計画法は、小さな部分問題を計算して得られた解をメモリに記録し、さらに大きい問題を解くためにそれら記録された結果を有効に使うことによって問題を解きます。 どちらも重要なプログラミング手法ですが、動的計画法は多くの問題の最適な解（最大値や最小値）を求めることができ、様々な問