Dynamic Programming • Bitmasking

Bitmasking + DP

Use integer bit operations to track sets of visited elements efficiently in state representations.

Overview

When the state space involves subsets of elements, we use bitmasks. A bit is 1 if an element is in the subset, 0 otherwise.

In TSP, the state is defined by the set of visited cities and the current city we are at: `dp[mask][u]`.

From city `u` with a given `mask`, we try visiting any unvisited city `v`. The new state becomes `dp[mask | (1 << v)][v]`.

Bitwise OR `|` adds an element to the set. Bitwise AND `&` checks if an element is present. This makes state management blazing fast.

Adjacency Cost Matrix (3x3):

dp[001][0]0

Code Tracker

:::

1dp[1][0] = 0;

2for (let mask = 1; mask < (1 << N); mask++) {

3 for (let u = 0; u < N; u++) {

4 if ((mask & (1 << u)) && dp[mask][u] != Infinity) {

5 for (let v = 0; v < N; v++) {

6 if (!(mask & (1 << v))) {

7 dp[mask | (1 << v)][v] = Math.min(

8 dp[mask | (1 << v)][v],

9 dp[mask][u] + cost[u][v]

10 );

11 }

12 }

13 }

14 }

15}