Изменения
→Оптимизация решения
Сама динамика будет такая: <br>
<tex>dpd[mask][i] = 1</tex>, если <tex>|mask| = 1</tex> и <tex>mask[i] = 1</tex> <br><tex>d[mask][i] = OR_{mask[j]=1, (j, i) \in E}d[mask \oplus 2^i][j]</tex>, если count(<tex>|mask)| > 1 </tex> и bit(<tex>mask[i, mask) ]= 1;</tex> <br>dp<tex>d[mask][i] = 0 </tex> во всех остальных случаях.<br>
Это решение, как и решение 2, требует O(2nn) памяти и O(2nn2) времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
