DP
動的計画法。問題を小さな部分問題に分割し、それらの解から元の問題の解を得る。
DP
をするために必要な要件は
部分最適性
があること。つまり部分問題の解が元の問題の解の一部になっている必要がある。