4个月前做过一道tsp的题目，仔细研究理解清楚了，但是不知道那个方法叫做状态压缩。过了4个月再次遇到的时候，一下子没有思路（还是不够熟悉）， 想了一会儿，知道这是tsp，也模糊的记起需要压缩一些状态，但是不是很确定，而且具体操作也一时没有捋清。 今天郑重整理一下这一类问题，同时把状态压缩的概念再强化一下。 首先这类问题还是遵循dp的思路，找到状态转移方程，找到最优子结构，还有无后效性。 只是其中关于状态存储变换这一部分可以进行适当的压缩，其余跟dp没有太大区别。 最后就是如果是需要返回路径的话，需要记录每个节点的前一节点，类似链表的形式。