其中1,2,3,4,5代表五个城市。此模型可抽象为图，可用邻接矩阵c表示，如下图所示：

 假设从顶点s出发，令d(i, V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

        推导：(分情况来讨论)

        ①当V为空集，那么，表示直接从i回到s了，此时 且 

        ②如果V不为空，那么就是对子问题的最优求解。你必须在V这个城市集合中，尝试每一个，并求出最优解。

           注：表示选择的城市和城市i的距离，是一个子问题。

        综上所述，TSP问题的动态规划方程就出来了：

现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)

这里只画出了d(1,{2,3,4}),由于篇幅有限这里就不画了。

①我们要求的最终结果是d(0,{1,2,3,4}),它表示，从城市0开始，经过{1,2,3,4}之中的城市并且只有一次，求出最短路径.。 ②d(0,{1,2,3,4})是不能一下子求出来的，那么他的值是怎么得出的呢？看上图的第二层，第二层表明了d(0,{1,2,3,4})所需依赖的值。那么得出：             ③d(1,{2,3,4})，d(2,{1,3,4})，d(3,{1,2,4})，d(4,{1,2,3})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3,4})       d(2,{1,3,4})，d(3,{1,2,4})，d(4,{1,2,3})同样需要这么求。     ④按照上面的思路，只有最后一层的，当V为空集时，就可以满足 且 该条件，直接求出dp数组部分的值。

由上述动态规划公式d(i,V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。根据上述给的测试用例有5个城市编号0,1,2,3,4。那么访问n个城市，恰好访问每个城市一次，并最终回到出发城市的嘴短距离可表示为d(0,{1,2,3,4}),那么问题来了我们用什么数据结构表示d(i,V)，这里我们就可二维数据dp[N][M]来表示，N表示城市的个数，M表示集合的数量，即,之所以这么表示因为集合V有个子集。根据测试用例可得出如下dp数组表格：

那么你们可能就有疑问了，为什么这么表示？这里说明一下比如集合{1,2,3,4}为什么用15表示，我们可以把 集合中元素看成二进制1的位置（二进制从右开始看），1表示从右开始第一位为1,2表示从又开始第二位为1，所以集合{1,2,3,4}可表示二进制（1111）转化为十进制为15。再举个例子比如集合{1,3}表示为二进制为0101，十进制为5。所以我们求出dp[0][15]（通用表示dp[0][]）就是本题的最终解。

注意：