動的計画法

動的計画法（DP）は、1957年にリチャード・ベルマンによって導入された、多段階意思決定問題を解くための厳密な最適化手法である。複雑な問題を単純で重複する部分問題に分解し、各部分問題を一度だけ解き、結果を保存して冗長な計算を回避する。最適性原理に基づき、問題が重複部分問題と最適部分構造を示す場合、DPは全体的な最適解を保証する。