#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/bitmask-dp

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/bitmask-dp

Repovive

Bitmask DP - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Bitmask DP

Using bits to represent state.

Bitmasks represent sets: bit $i$ indicates element $i$ membership.

TSP example: dp[mask][i] = min cost visiting cities in mask, ending at $i$ .

for mask from 0 to 2^n - 1:
    for last in mask:
        for next not in mask:
            newMask = mask | (1 << next)
            dp[newMask][next] = min(dp[newMask][next],
                                    dp[mask][last] + dist[last][next])

Time: $O(n^2 \cdot 2^n)$ . Space: $O(n \cdot 2^n)$ . Feasible for $n \leq 20$ .