Die Bitmask-DP-Intuition, die ich mit 14 gerne gehabt hätte.

Als ich zum ersten Mal Bitmask-DP gesehen habe, habe ich mir das Muster gemerkt: dp[mask][last], über Submasken iterieren, fertig. Damit habe ich ein paar Aufgaben bestanden. Dann bin ich auf eine gestoßen, die leicht anders war, und hatte keine Ahnung, was ich tun sollte, weil ich ein Rezept gelernt hatte, ohne zu verstehen, wofür irgendeine der Zutaten war.

Das ist es, was ich mir gewünscht hätte, dass mir damals jemand gesagt hätte: Die Bitmaske ist nicht der Punkt. Die Bitmaske ist nur eine kompakte Art, eine ganz bestimmte Art von Zustand zu kodieren. Die eigentliche Fähigkeit ist Zustandsdesign — herausfinden, welche Information du tatsächlich weitertragen musst. Sobald du das hast, ist die Bitmaske nur eine Fußnote.

Was bedeutet „Zustand"?

Bei jeder DP muss dein Zustand eine Frage beantworten: Angesichts von allem, worauf ich mich bisher festgelegt habe — was muss ich noch entscheiden, und was kostet es von hier aus?

Das Wort „festgelegt" leistet hier viel Arbeit. Du cachst kein Ergebnis — du fasst eine Teilkonstruktion gut genug zusammen, dass du sie optimal fortsetzen kannst, ohne auf die Geschichte zurückzuschauen.

Bitmask-DP taucht auf, wenn die Menge der Dinge, auf die du dich festgelegt hast, zählt, die Reihenfolge aber meist nicht — oder wenn du genau verfolgen musst, welche Elemente du bereits verwendet hast. Bei N ≤ 20 oder so kannst du „Ich habe die Elemente {0, 2, 5} verwendet" als die Ganzzahl 0b100101 darstellen. Das war's. Der Rest ist einfach DP auf Teilmengen.

Aufgabe (a): Hamiltonpfad

Klassiker. Du hast N ≤ 20 Knoten, einen gerichteten Graphen, und willst wissen, ob es einen Pfad gibt, der jeden Knoten genau einmal besucht. (CSES „Hamiltonian Flights" ist eine Version; das AtCoder-DP-Aufgabenset hat einen Matching-artigen Verwandten.)

Der falsche Weg, darüber nachzudenken: „Ich muss mir merken, welche Knoten ich besucht habe." Das stimmt, aber das ist kein Zustandsdesign — das ist eine Wunschliste.

Die richtige Frage: Kann ich, nachdem ich eine Teilmenge S von Knoten besucht habe und bei Knoten v ende, das zu einem Hamiltonpfad erweitern? Mein Zustand ist (mask, v) — mask ist die Menge der besuchten Knoten, v ist, wo ich gerade bin. Ich lege mich auf beides gleichzeitig fest.

// 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;
            }
        }
    }
}

Der Übergang ist: Wenn ich bei v bin und mask besucht habe, kann ich zu jedem unbesuchten Nachbarn u wechseln, was den Zustand (mask | (1 << u), u) erzeugt. Beachte, dass sich der Übergang direkt aus der Zustandsdefinition ergibt — ich habe nicht zuerst über Übergänge nachgedacht. Ich habe über den Zustand nachgedacht, und der Übergang wurde offensichtlich.

Aufgabe (b): Zuordnung / Matching

N Jobs, N Arbeiter, Kostenmatrix. Weise jeden Job genau einem Arbeiter zu, minimiere die Gesamtkosten. Das ist AtCoder-DP-„O - Matching"-Terrain, oder das klassische Zuordnungsproblem, wenn N klein ist.

Hier sieht der Zustand etwas anders aus. Ich verarbeite Jobs einzeln nacheinander. Nachdem ich die Jobs 0..k-1 behandelt habe, ist mein Zustand: Welche Arbeiter habe ich schon zugewiesen? Das ist die mask. Der Job-Index ist implizit — er ist einfach popcount(mask), die Anzahl gesetzter Bits, weil ich Jobs der Reihe nach zuweise.

// 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]);
    }
}

Gleiche Form, andere Interpretation. Die mask bedeutet „festgelegte Arbeiter". Der Job-Index wird kostenlos aus der mask zurückgewonnen. Das lohnt sich, kurz innezuhalten — viele Bitmask-DP-Zustände tragen implizite Information, die du nicht separat speichern musst.

Aufgabe (c): TSP-Rundtour

Jetzt kommt die Anforderung dazu, dass du nach dem Besuch aller N Knoten zum Start zurückkehrst und dabei das Gesamtkantengewicht minimierst. Das ist das Problem des Handlungsreisenden bei kleinem N.

Der Zustand ist immer noch (mask, v) — genau wie beim Hamiltonpfad. Was sich ändert, ist die Antwortextraktion: Nachdem die volle mask gefüllt ist, prüfe ich die Kosten für die Rückkehr nach Hause. Die zugrunde liegende DP ist identisch. Das Einzige, was ich anpassen musste, war, was ich am Ende gefragt habe.

Wenn du in einem Satz benennen kannst, was dein Zustand bedeutet — „die Menge der festgelegten Entscheidungen und die aktuelle Position" — ist die Bitmaske das kleinste Detail. Alles andere folgt aus diesem Satz.

Schüler, die sich dp[mask][last] merken, ohne zu verstehen, was mask und last darstellen, bleiben in dem Moment stecken, in dem eine Aufgabe nicht exakt in die Vorlage passt. Mira, eine meiner Schülerinnen, hat zwei Stunden an einer Subset-Sum-Variante verbracht, bevor wir durchgesprochen haben, was „festgelegt" in diesem Kontext bedeutet — sobald sie den Zustand als „die Teilmenge der Elemente, die ich schon platziert habe" umformuliert hat, war die Lösung zehn Zeilen lang.

Die eigentliche gedankliche Checkliste

Wenn ich eine Aufgabe sehe und Bitmask-DP vermute, stelle ich mir diese Fragen der Reihe nach:

1. Was baue ich auf? (eine Permutation, eine Zuordnung, eine Teilmenge, eine Rundtour)
2. Welche Teilinformation muss ich mitführen, um künftig optimale Entscheidungen zu treffen? Das ist mein Zustand.
3. Lässt sich diese Information als Teilmenge einer kleinen Menge kodieren (N ≤ 20)? Dann ist die mask nur die Art, wie ich sie darstelle.
4. Wie sieht ein Übergang aus? (Ein weiteres Element hinzufügen, eine weitere Zuordnung treffen.)
5. Was ist der Basisfall — die leere Festlegung?

Die Bitmaske ist keine Technik. Sie ist eine Datenstruktur-Wahl, um eine bestimmte Art von Zustand darzustellen. Bekomme den Zustand richtig hin, und du hast den schweren Teil erledigt. Die Ganzzahl-Arithmetik — mask | (1 << i), mask & (1 << i), das Iterieren über Submasken — ist mechanisch und an einem Nachmittag erlernbar.

Wenn du dich auf die OI vorbereitest und Bitmask-DP schon gesehen hast, es sich aber noch nicht solide anfühlt, wähle eine Aufgabe — die Zuordnungsaufgabe ist am saubersten — und schreib, bevor du irgendeinen Code schreibst, in Worten auf, was dein Zustand darstellt. Zwing dich, präzise zu sein. „dp[mask] sind die minimalen Kosten, um die ersten popcount(mask) Jobs mit genau den Arbeitern in mask zuzuweisen." Wenn du diesen Satz schreiben kannst, kannst du den Code schreiben.