動的計画法とは

動的計画法とは、問題をより小さな部分問題に分け、部分問題の解を表などに記録しておき、同じ部分問題が再び必要になったときは計算し直さずに記録を再利用することで、効率よく解を求める手法である。