Intuicja bitmask DP, którą chciałbym mieć w wieku 14 lat.

Kiedy pierwszy raz zobaczyłem bitmask DP, zapamiętałem wzorzec: dp[mask][last], iteruj po submaskach, gotowe. Zaliczyłem z tym kilka zadań. Potem trafiłem na takie, które było odrobinę inne, i nie miałem pojęcia, co robić, bo nauczyłem się przepisu, nie rozumiejąc, do czego służy którykolwiek ze składników.

Oto rzecz, którą chciałbym, żeby ktoś mi wtedy powiedział: bitmaska nie jest sednem sprawy. Bitmaska to tylko zwarty sposób zakodowania jednego konkretnego rodzaju stanu. Prawdziwą umiejętnością jest projektowanie stanu — rozgryzienie, jaką informację faktycznie musisz nieść dalej. Gdy już to masz, bitmaska jest tylko przypisem.

Co właściwie znaczy „stan”?

W każdym DP twój stan musi odpowiadać na jedno pytanie: biorąc pod uwagę wszystko, do czego dotąd się zobowiązałem, co jeszcze muszę zdecydować i ile to kosztuje od tego miejsca?

Słowo „zobowiązałem się” wykonuje tu dużo pracy. Nie buforujesz wyniku — podsumowujesz częściową konstrukcję na tyle dobrze, że możesz ją kontynuować optymalnie, nie oglądając się na historię.

Bitmask DP pojawia się, gdy liczy się zbiór rzeczy, do których się zobowiązałeś, ale zwykle nie liczy się kolejność — albo gdy musisz śledzić dokładnie, których elementów użyłeś. Przy N ≤ 20 czy około tego, możesz przedstawić „użyłem elementów {0, 2, 5}” jako liczbę całkowitą 0b100101. I tyle. Reszta to zwyczajne DP na podzbiorach.

Zadanie (a): ścieżka Hamiltona

Klasyk. Masz N ≤ 20 wierzchołków, graf skierowany, i chcesz wiedzieć, czy istnieje ścieżka odwiedzająca każdy wierzchołek dokładnie raz. (CSES „Hamiltonian Flights” to jedna wersja; zestaw zadań AtCoder DP ma kuzyna w klimacie kojarzenia.)

Zły sposób myślenia o tym: „muszę pamiętać, które wierzchołki odwiedziłem”. To prawda, ale to nie jest projekt stanu — to lista życzeń.

Właściwe pytanie: po odwiedzeniu pewnego podzbioru S wierzchołków, kończąc w wierzchołku v, czy mogę to rozszerzyć do ścieżki Hamiltona? Mój stan to (mask, v) — mask to zbiór odwiedzonych wierzchołków, v to miejsce, w którym teraz jestem. Zobowiązuję się do obu jednocześnie.

// dp[mask][v] = true if we can visit exactly the vertices in mask,
//               ending at vertex v
bool dp[1 << N][N];

dp[1 << start][start] = true;

for (int mask = 0; mask < (1 << N); mask++) {
    for (int v = 0; v < N; v++) {
        if (!dp[mask][v]) continue;
        for (int u = 0; u < N; u++) {
            if (mask & (1 << u)) continue; // already visited
            if (has_edge[v][u]) {
                dp[mask | (1 << u)][u] = true;
            }
        }
    }
}

Przejście wygląda tak: jeśli jestem w v po odwiedzeniu mask, mogę przejść do dowolnego nieodwiedzonego sąsiada u, uzyskując stan (mask | (1 << u), u). Zwróć uwagę, że przejście wynika wprost z definicji stanu — nie myślałem najpierw o przejściach. Myślałem o stanie, a przejście stało się oczywiste.

Zadanie (b): przydział / kojarzenie

N zadań, N pracowników, macierz kosztów. Przydziel każde zadanie do dokładnie jednego pracownika, minimalizując łączny koszt. To teren AtCoder DP „O - Matching”, czyli klasyczny problem przydziału, gdy N jest małe.

Tutaj stan wygląda nieco inaczej. Przetwarzam zadania jedno po drugim. Po obsłużeniu zadań 0..k-1 mój stan to: których pracowników już przydzieliłem? To jest mask. Indeks zadania jest niejawny — to po prostu popcount(mask), czyli liczba ustawionych bitów, bo przydzielam zadania po kolei.

// dp[mask] = minimum cost to assign the first popcount(mask) jobs
//            using exactly the workers in mask
long long dp[1 << N];

dp[0] = 0;

for (int mask = 0; mask < (1 << N); mask++) {
    int job = __builtin_popcount(mask); // which job are we assigning?
    if (job == N) continue;
    for (int w = 0; w < N; w++) {
        if (mask & (1 << w)) continue; // worker already used
        dp[mask | (1 << w)] = min(dp[mask | (1 << w)],
                                   dp[mask] + cost[job][w]);
    }
}

Ten sam kształt, inna interpretacja. Mask oznacza „pracowników, do których się zobowiązałem”. Indeks zadania odzyskujesz z maski za darmo. Warto się nad tym zatrzymać — wiele stanów w bitmask DP niesie niejawną informację, której nie musisz przechowywać osobno.

Zadanie (c): zamknięta trasa komiwojażera

Teraz dodaj wymóg, że po odwiedzeniu wszystkich N wierzchołków wracasz do punktu startowego, minimalizując łączną wagę krawędzi. To problem komiwojażera przy małym N.

Stan to nadal (mask, v) — tak samo jak w ścieżce Hamiltona. Zmienia się wydobycie odpowiedzi: po wypełnieniu pełnej maski sprawdzam koszt powrotu do domu. Leżące u podstaw DP jest identyczne. Jedyną rzeczą, którą musiałem zmienić, było to, o co pytam na końcu.

Kiedy potrafisz nazwać, co znaczy twój stan, w jednym zdaniu — „zbiór podjętych decyzji i aktualna pozycja” — bitmaska jest najmniej istotnym szczegółem. Wszystko inne wynika z tego zdania.

Uczniowie, którzy zapamiętują dp[mask][last], nie rozumiejąc, co reprezentują mask i last, utkną w momencie, gdy zadanie nie pasuje dokładnie do szablonu. Mira, jedna z moich uczennic, spędziła dwie godziny nad wariantem subset-sum, zanim omówiliśmy, co w tym kontekście znaczy „zobowiązanie” — gdy tylko przeformułowała stan jako „podzbiór elementów, które już umieściłam”, rozwiązanie miało dziesięć linijek.

Rzeczywista lista kontrolna w głowie

Kiedy widzę zadanie i podejrzewam bitmask DP, zadaję sobie po kolei te pytania:

1. Co buduję? (permutację, przydział, podzbiór, trasę)
2. Jaką częściową informację muszę nieść dalej, żeby podejmować optymalne decyzje? To jest mój stan.
3. Czy tę informację można zakodować jako podzbiór jakiegoś małego zbioru (N ≤ 20)? Wtedy maska to po prostu sposób, w jaki ją reprezentuję.
4. Jak wygląda jedno przejście? (Dodaj jeszcze jeden element, wykonaj jeszcze jeden przydział.)
5. Jaki jest przypadek bazowy — puste zobowiązanie?

Bitmaska nie jest techniką. To wybór struktury danych do reprezentowania konkretnego rodzaju stanu. Ustal poprawnie stan, a masz za sobą trudną część. Arytmetyka na liczbach całkowitych — mask | (1 << i), mask & (1 << i), iterowanie po submaskach — jest mechaniczna i da się jej nauczyć w jedno popołudnie.

Jeśli przygotowujesz się do OI i widziałeś już bitmask DP, ale wciąż nie czujesz się w nim pewnie, wybierz jedno zadanie — najczystsze jest to o przydziale — i zanim napiszesz choć linijkę kodu, zapisz słowami, co reprezentuje twój stan. Zmuś się do precyzji. „dp[mask] to minimalny koszt przydzielenia pierwszych popcount(mask) zadań przy użyciu dokładnie pracowników z mask”. Jeśli potrafisz napisać to zdanie, potrafisz napisać kod.