Patterns

DP where state is a bitmask representing which items have been used/visited

When to useTraveling salesman variants, assignment problems with small N (≤20), subset enumeration with optimization

DECLARE

dp = new Array(1 << n).fill(Infinity)

const m = bikes.length;
const n = workers.length;
const dp = new Array(1 << m).fill(Infinity);

const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));

BASE CASES

dp[0] = 0 (empty set)

dp[0] = 0;

dp[1][0] = 0;

BUILD

for mask from 0 to (1 << n) - 1; for each unset bit i

for (let mask = 0; mask < (1 << m); mask++) {

for (let mask = 1; mask < (1 << n); mask++) {

[RECURRENCE]

dp[mask | (1 << i)] = min(dp[next], dp[mask] + cost(i, mask))

    if (mask & (1 << b)) continue;
    const next = mask | (1 << b);
    dp[next] = Math.min(dp[next], dp[mask] + dist(workers[w], bikes[b]));

    for (let next = 0; next < n; next++) {
      if ((mask & (1 << next)) || graph[node][next] === 0) continue;
      const nm = mask | (1 << next);
      dp[nm][next] = Math.min(dp[nm][next], dp[mask][node] + graph[node][next]);
    }

RETURN

return dp[(1<<n) - 1]

let ans = Infinity;
for (let mask = 0; mask < (1 << m); mask++) {
  if (popcount(mask) === n) ans = Math.min(ans, dp[mask]);
}
return ans;

const FULL = (1 << n) - 1;
let best = Infinity;
for (let node = 0; node < n; node++) best = Math.min(best, dp[FULL][node]);
return best === Infinity ? -1 : best;