Example input

In the previous article, we discussed classic dynamic programming problems and their solutions, mastering how to apply dynamic programming to solve common optimization problems. This article delves into a more advanced dynamic programming technique—bitmask dynamic programming (also known as state-compression DP). Bitmask DP is particularly useful for problems with extremely large state spaces; by compressing states efficiently—typically using bit operations—it makes computation both more efficient and practically feasible.

What Is Bitmask Dynamic Programming?

The core idea of bitmask dynamic programming is to use bitwise operations to compress the state space. In standard dynamic programming, a state is often defined by multiple variables. Bitmask techniques encode such multi-variable states into a single integer—usually interpreted as a binary number—where each bit represents whether a particular element (e.g., an item or node) is included in the current state. This dramatically reduces memory usage and computational overhead.

Typical Use Cases

Bitmask DP is especially well-suited for the following scenarios:

1. Subset-related problems: When states correspond naturally to subsets of a given set.
2. Small-scale data: When the number of elements (e.g., cities, items) is modest enough (typically ≤ 20) to allow representation via bitmasks.
3. High-dimensional but bounded-state problems: When the DP state has many dimensions, yet each dimension takes only a small number of possible values (e.g., binary on/off flags).

Case Study: Solving the Traveling Salesman Problem (TSP) with Bitmask DP

Problem Description

The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits each city exactly once and returns to the starting city. A natural DP formulation uses dp[mask][i], representing the minimum cost to reach city i having visited exactly the subset of cities encoded by the bitmask mask.

State Definition

• mask: An integer whose binary representation has length n (number of cities); the k-th bit is 1 if city k has been visited, and 0 otherwise.
• i: The index of the current (last visited) city.

State Transition Equation

The recurrence relation is:

Here, j ranges over all cities already visited in mask except i, and dist[j][i] denotes the distance from city j to city i. Note that mask \setminus \{i\} corresponds to clearing the i-th bit: mask ^ (1 << i).

Initialization

Assume the tour starts at city 0. Then the initial state is:

(since 1 in binary is 00...01, indicating only city 0 has been visited).

Final Answer

After computing all states, the answer is the minimum cost to return to city 0 after visiting all cities:

where all_visited = (1 << n) - 1 (i.e., a bitmask with all n bits set to 1).

Code Implementation

Below is a Python implementation of the TSP solution using bitmask DP:

import sys

def tsp(n, dist):
    # dp[mask][i]: min cost to visit cities in 'mask', ending at city i
    INF = sys.maxsize
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    # iterate over all masks
    for mask in range(1 << n):
        for i in range(n):
            # if city i is included in mask
            if mask & (1 << i):
                # try coming from each previously visited city j ≠ i
                for j in range(n):
                    if mask & (1 << j) and j != i:
                        prev_mask = mask ^ (1 << i)  # remove city i from mask
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    all_visited = (1 << n) - 1  # all n bits set
    # return to city 0 from any city i (i ≠ 0)
    ans = min(dp[all_visited][i] + dist[i][0] for i in range(1, n))
    
    return ans

# Example input
cities = 4
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

result = tsp(cities, distances)
print("Minimum tour cost:", result)

Summary

By applying bitmask dynamic programming, we effectively compress the exponential state space of the TSP into a manageable size—reducing both time and memory complexity significantly. This technique proves powerful across numerous combinatorial optimization problems, especially those involving subsets, permutations, or constrained selections.

In the next article, we will explore greedy algorithms, covering their foundational principles and practical applications—and learn when and how to leverage greedy strategies to design efficient, intuitive solutions. We hope this article equips you with fresh perspectives and powerful tools for tackling future algorithmic challenges!