次の状態定義を用いる動的計画法によって解くことができます。

• \(cost[n][i]\)：すでに訪れた都市の集合が \(n\) であって、最後にいる都市が \(i\) であるときの、合計コストの最小値。

\(n\) は都市のインデックスからなる集合ですが、整数の二進数表記を考えることで集合と整数を対応付けることができます。