确实有一种O（n2 n）动态编程算法可以找到哈密顿循环。这个想法可以减少许多O（n！）回溯到O（n 2 2 n）或O（n2
n）（以使用更多内存为代价）的一般想法，它是考虑 设置 子问题 具有指定的“端点” 。

在这里，由于需要一个循环，因此可以从任何顶点开始。因此，修复一个，称之为x。子问题是：“对于一个给定S和顶点v的S，是有一个路径开始x，并通过所有的顶点会S在结束v？”
称此为poss[S][v]。

与大多数动态编程问题一样，一旦定义了子问题，其他问题就显而易见了：以任何“递增”顺序循环遍历所有2
n个顶点集S，对于每个这样的S中的每个v，您都可以计算poss[S][v]为：

poss [S] [v] =（u在S中存在一些，使得poss [S- {v}] [u]为True且u->v存在边）

最后，存在哈密顿循环，前提是存在一个顶点v，使得v->x存在边且该边poss[S][v]为True，S所有顶点的集合在哪里（除了x，取决于您如何定义它）。

如果您想要实际的哈密顿循环而不是仅仅确定一个循环是否存在，请poss[S][v]存储u使之成为可能的实际循环，而不仅仅是True或False。这样，您可以追溯到最后的路径。