​ 旅行商问题（Travelling Salesman Problem, 简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[dij]，其中dij表示城市i到城市j的距离，i，j=1，2 … n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。

​ 要使用动态规划，需要问题本身有最优子结构，我们需要找到要解决的问题的子问题。题目要求，从0(a)出发，经过[1(b),2©,3(d)]这几个城市，然后回到0，使得花费最少。要实现这个要求，需要从下面三个实现方案中选择花费最少的方案。

​ 从0出发，到1，然后再从1出发，经过[2,3]这几个城市，然后回到0，使得花费最少。 ​ 从0出发，到2，然后再从2出发，经过[1,3]这几个城市，然后回到0，使得花费最少。 ​ 从0出发，到3，然后再从3出发，经过[1,2]这几个城市，然后回到0，使得花费最少。 ​ 可以发现，三个小的解决方案的最优解，构成了大的解决方案，所以这个问题具有最优子结构，可以用动态规划来实现。

​ 设置一个二维的动态规划表dp,定义符号{1,2,3}表示经过[1,2,3]这几个城市，然后回到0。 ​ 设置一个二维数组l保存两个城市之间的距离。 ​ 那么题目就是求dp[0][{1,2,3}]。将{1,2,3}表示成二进制，就是111，对应10进制的7，所以题目是在求dp[0][7];

​ 要求三个方案的最小值意味：

​ dp[0][{1,2,3}] = min{l[0][1]+dp[1][{2,3}] ，l[0][2]+dp[2][{1,3}] ，l[0][3]+dp[3][{1,2}]} ​ dp[1][{2,3}] = min{ l[1][2]+dp[2][{3}] ，l[1][3]+dp[3][{2}]} ​ dp[2][{3}] = l[2][3]+dp[3][{}] ​ dp[3][{}]就是从3出发，不经过任何城市，回到0的花费，所以dp[3][{}] = l[3][0]