別に全探索でもDPでもそんなに変わらなくない?
緩和の式自明だし