we discuss the traveling salesman problem. In this problem, we have an undirected weighted graph where the vertices represent cities and the weights represent the cost to travel between cities since the graph is undirected, the cost to travel from one city to another is the same in both directions. The goal 8 the problem is to reduce the cost of visiting  each city in a tour. We start from a city and return back to the city.
We solve this problem by dynamic programming.

• For any set s belonging to V such that t belongs to S, we compute a quantity M[s, k] which represents the minimum cost of travel from a vertex t, visiting each vertex in S and then visiting k
• M [s, k] is the minimum cost = w (1, k) is s = 1, k or it is M [s - k, m ] +w (m, k)

We could also write an equivalent using memoziation 

minTSP (v):

Best = infinity 

for k = 2 to N 

       Best = min ( Best, memo (s, V), w (1, k) )

return next 

memo(s, k):

  

If M (s, k) is defined 

    Return M (s, k)

If s == 2

    Return M (s, k) = w (1, k)

Best = infinity

 For all m not = 1 in S - k

    Best = min ( Best, Memo({s}-k, m), w (m, k) )

Return M (s, k) = Best