动态规划求解TSP的复杂度是什么

动态规划求解TSP的时间复杂度是O(n^2 * 2^n)，其中n表示城市的数量。这是因为，在动态规划求解TSP的过程中，需要枚举所有可能的子集以及子集中的所有城市，而每个子集的大小为2的n次方。同时，对于每个子集，需要计算出从起点出发经过该子集中所有城市且最终回到起点的最短路径长度，这需要进行一次O(n^2)的计算。因此，动态规划求解TSP的总时间复杂度为O(n^2 * 2^n)。