DPって全探索の効率化だから、元となる全探索アルゴリズムから考えればそうなるよ