動的計画法 Dynamic Programming

問題を解く有効な手法の１つが、最終的な解を求めるために、その問題の小さな部分問題の解を用いることです。一般的に小さな問題はより容易に分析・解決できるものです。この手法の代表的なものに、分割統治法（Divide and Conquer)と動的計画法 (Dynamic Programming: DP)があります。

分割統治法では問題を２つ（またはそれ以上）に分け、それらをそれぞれ解き、元の問題を解くためにそれらの分割して解かれた問題を統合して利用する、という処理を再帰的に行います。マージソートが分割統治法のよい例です。

一方動的計画法は、小さな部分問題を計算して得られた解をメモリに記録し、さらに大きい問題を解くためにそれら記録された結果を有効に使うことによって問題を解きます。

どちらも重要なプログラミング手法ですが、動的計画法は多くの問題の最適な解（最大値や最小値）を求めることができ、様々な問題に応用できる実用的なアルゴリズムです。

• Fibonacci Number フィボナッチ数


• Warshall Floyd's algorithm


• Longest Increasing Subsequence 最長増加部分列 O(n²)


• Longest Increasing Subsequence 最長増加部分列 O(nlogn)


• Longest Common Subsequence 最長共通部分列


• 0-1 Knapsack Problem ナップザック問題


• 0123 Knapsack Problem


• Edit Distance


• Maximum Sum (1D)


• Maximum Sum (2D)


• Largest Squere


• Largest Rectangle


• Matrix Chain Multiplication 連鎖行列積


• Traveling Salesman Problem (TSP) 巡回セールスマン問題


• Partition Problem

DP は、システムエンジニアやプログラマの方にとっては、必ず習得すべきプログラミングテクニックの１つだと思います。しかし、与えられた問題に DP が適用できるか否かの判断は難しいので、ある程度の経験が必要です。つまり、小さな問題の解を利用することによって、大きな問題の解が正しく求めることができるか否かの判断が難しいのです。

DP のスキルを伸ばすためには、DP が適用できる典型的な問題を解いてみるのが良いと思います。以下に応用問題をあげます（解法バレ注意してください）。

• The Secret Number


• Atomic Car Race


• Sum of Different Primes