Editing Hamiltonian path problem (section)

=== Dynamic programming ===
Also, a [[dynamic programming]] algorithm of [[Held-Karp algorithm|Bellman, Held, and Karp]] can be used to solve the problem in time O(''n''<sup>2</sup> 2<sup>''n''</sup>). In this method, one determines, for each set ''S'' of vertices and each vertex ''v'' in ''S'', whether there is a path that covers exactly the vertices in ''S'' and ends at ''v''. For each choice of ''S'' and ''v'', a path exists for (''S'',''v'') if and only if ''v'' has a neighbor ''w'' such that a path exists for (''S'' − ''v'',''w''), which can be looked up from already-computed information in the dynamic program.<ref>{{Cite journal |last=Bellman |first=Richard |date=January 1962 |title=Dynamic Programming Treatment of the Travelling Salesman Problem |journal=Journal of the ACM |language=en |volume=9 |issue=1 |pages=61–63 |doi=10.1145/321105.321111 |s2cid=15649582 |issn=0004-5411|doi-access=free }}</ref><ref>{{Cite journal |last1=Held |first1=Michael |last2=Karp |first2=Richard M. |date=March 1962 |title=A Dynamic Programming Approach to Sequencing Problems |url=http://epubs.siam.org/doi/10.1137/0110015 |journal=Journal of the Society for Industrial and Applied Mathematics |language=en |volume=10 |issue=1 |pages=196–210 |doi=10.1137/0110015 |issn=0368-4245}}</ref>