状态压缩DP
状态压缩DP是一种动态规划方法，它通过将每一种状态压缩成一个数来表示，一般用二进制来表示。这种方法适用于状态数量不是很多的情况。状态压缩DP的核心思想是利用二进制表示状态，每个位代表一个状态变量的两种可能情况（例如，0和1），每一位都有0/1两个状态，那么n位数，就有2^n种状态，通过二进制数的每一位上的变化来表示不同的状态。
状态压缩DP的关键在于如何定义状态以及如何进行状态转移。在定义状态时，通常会使用一个整数的二进制表示来表示一组状态，例如在01背包问题中，可以用一个二进制数的每一位来表示一件物品是否被选中。在状态转移时，需要考虑如何从一个状态转移到另一个状态，这通常涉及到枚举子集或超集，并根据问题的特点更新状态的值。
状态压缩DP的使用场景通常包括：
1. 状态的组合需要有很多状态的组成，由二进制位数确定，即一个状态应该是保存一个集合，其中的元素值对应着0或1。
2. 题目中限制的集合大小不会超过20，因为如果用二进制表示状态，那么集合大小为20的二进制状态有2^20 - 1个，已经达到一个很大的数量级。
3. 具有动态规划的特性，即要求最优化某个值，具有最优子结构的性质。
在实际应用中，状态压缩DP可以用于解决很多问题，其中每个状态可以通过二进制数来表示每一种不同的情况，然后通过动态规划来计算答案。
原题链接：731. 毕业旅行问题 - AcWing题库
此题难度较大，是2019年字节跳动校招题，里面涉及位运算与状态压缩DP，不会的可以去学习，此题根据个人量力而行。
建议看一下y总的讲解：AcWing 731. 毕业旅行问题（每日一题）_哔哩哔哩_bilibili
题目：
小明目前在做一份毕业旅行的规划。
打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。
由于经费有限，小明希望能够通过合理的路线安排尽可能的省些路上的花销。
给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
注意：北京为 1 号城市。
输入格式
第一行包含一个正整数 n，表示城市个数。
接下来输入一个 n 行 n列的矩阵，表示城市间的车票价钱。
输出格式
输出一个整数，表示最小车费花销。
数据范围
1<n≤20,包括北京
车票价格均不超过 1000 元。
输入样例：
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0
输出样例：
13
说明
共 4 个城市，城市 1 和城市 1 的车费为 0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，以此类推。
假设任意两个城市之间均有单程票可买，且价格均在 1000 元以内，无需考虑极端情况。
解题思路：
此题主要用了状态压缩DP，它的f[i,j]设置的很巧妙，把i化成二进制，比如有五个城市，初始为00001，最后一位为北京当前就在北京。下一个比如武汉花费小（武汉第三个城市）那就是二进制为00101，又到达上海（第五个城市）那就是10101……当达到目标状态二进制为11111，把所有城市都标记一遍，那么此次完成了此次旅行，还一个问题那就是我还要回北京啊，既然要回北京那就要找最后一个到达的城市，从最后到达的城市坐高铁直接回北京，那么我们最后还要枚举一遍最后到达的城市，在所有城市里面加上回北京的费用，取一个最小值即是答案。
一些细节问题以及一些位运算等问题以图片手写解答一下：
代码实现：
#include<iostream> #include<cstring> using namespace std; const int N=20,M=1<<N,inf=0x3f3f3f; int n; int w[N][N],f[M][N];//w[i][j]表示花费数组 //f[i][j]表示i为二进制标记数组，j表示到达j个城市的最小花费 int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>w[i][j]; } } memset(f,inf,sizeof(f));//初始无穷大 f[1][0]=0;//2^0=1第一个北京地点被标记为1 for(int i=1;i<1<<n;i+=2){//1~2^n都遍历一遍 //i+2是把第一个北京也给同时被标记，加一二进制逢二进一，会变成10，北京又被置成0没有被标记，所以加2还是1 for(int j=0;j<n;j++){//j遍历到达第j个城市 if(i>>j&1){//此时处于j城市，看看是否i中包含j(被标记)，i的二进制表示第j位是否为1 for(int k=0;k<n;k++){//k表示中转城市到达j城市 if(i-(1<<j)>>k&1){//判断第i个状态除去第j个城市是否包含第k个城市 f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]); } } } } } int res=inf; for(int i=1;i<n;i++){//枚举最后一个到达的城市 res=min(res,f[(1<<n)-1][i]+w[i][0]);//为了二进制方便下标从0开始 } cout<<res<<endl; return 0; }
写在最后：
此题对于博主这样的cj来说比较难了，都是按照博主自己的理解去写的，会有一些不是很准确的地方，学了很长时间，似懂非懂的感觉，大佬勿喷。主要还是状态的定义利用二进制去标记那个地方第一次见，感觉很巧妙，再就是写代码中不经常使用位运算对于y总的代码看起来也比较困难，还有很多地方需要好好学习一次，感觉跟着y总的每日一题学到了不少东西，以后还需继续加油，文章若有错误的地方请各位大佬指出，一起学习进步。
执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。。
