DP-on-Bits Academy - Bitmask DP Introduction

📚 Bitmask DP Concepts

Bitmask DP uses bits to represent subset states. Each bit represents whether an item/task is included (1) or excluded (0).

          // Common Bitmask DP Operations:

          // Check if task i is done:

          isDone = (mask & (1 << i)) != 0

          // Complete task i:

          newMask = mask | (1 << i)

          // Undo task i:

          newMask = mask & ~(1 << i)

          // Count completed tasks:

          count = popcount(mask)

          // Check all tasks done:

          allDone = (mask == (1 << n) - 1)

Applications: Traveling Salesman Problem, Assignment Problem, Subset Sum, Hamiltonian Path, etc.