Bitmask Dynamic Programming

В тази секция ще разгледаме какво представлява "битова маска" и как тя се ползва като измерение в стейта на динамични задачи. Това е една от най-популярните разновидности на динамичното оптимиране и е гарантирано, че рано или късно ще срещнете такива задачи в състезания. Маската не е задължително да е двоична (макар и това да е най-честия случай) - понякога може да е четвъртична (като за всеки елемент от множеството се пазят по два бита) или троична (в който случай трябва да кодираме стейта ръчно).

За тази секция ще ви е полезно да разгледате темата за побитови операции и, разбира се, Динамично оптимиране, част III.

Задачите в секцията се решават с динамично оптимиране, като едно (или повече) от измеренията са битови маски или числа в троична/четвъртична бройна система.