Subset DP is dynamic programming indexed by subsets of a finite ground set, usually encoded by bit masks. A recurrence builds a subset from smaller subsets or removes one chosen element. There are subsets of an -element set, so many such methods require exponential space or time despite avoiding factorial enumeration.
For a shortest path visiting a given set, stores the best cost of a path visiting exactly and ending at . The recurrence retains the endpoint because it controls the next edge cost. Initial states and prohibited edges must be specified separately.

Articles by others on the same topic (0)

There are currently no matching articles.