【以下内容仅为本人在学习中的所感所想，本人水平有限目前尚处学习阶段，如有错误及不妥之处还请各位大佬指正，请谅解，谢谢！】
引言
动态规划虽然已经是对暴力算法的优化，但在某些比较特别的情况下，可以通过一些小技巧进一步对其优化，通产我们会在时间与空间中做权衡，在时间可以接受度范围内，适当的以时间为代价换取更小空间的占用；在不爆空间的情况下，适当的以空间换时间。在此，本人将以目前总结的经验详细介绍状态压缩与状压DP。
状态压缩
（一）状态
状态指某个事物表现出来的形态（百度百科）。联系前面的文章（有关动态规划 - PaperHammer - 博客园 (cnblogs.com)），我们在分析解决动态规划的问题时，其重点是在“分情况定变量”这一步，即有多少种选择，如何选择。不妨把这每一个选择视为一个事物，则它表现出来的形态就是所做出的选择，更进一步就是选择的结果。所以，动态规划中的状态实际上就是每一种情况。
（二）压缩
压缩是一种通过特定的算法来减小计算机文件大小的机制，其目的是减少所占空间的同时提高运算速度（百度百科）。压缩的本质是减小，但不可否认虽然减小了文件体积提高了传输速度，但会存在文件质量的下降。
（三）状态压缩
一般地，我们规定利用计算机的二进制性质来描述所做出的选择，即将所有情况统一分为：行或不行、放或不放等两种情况（将很多情况归于两类情况）。由此可以发现，对于状态压缩，我们是针对有多少种选择进行了压缩，即对空间进行优化，那么根据互斥性原则（自己编的名字），对空间上的优化势必会带来时间上的复杂。所以，状态压缩在时间上其实是一种很暴力的思想，它需要遍历每一种情况，每种情况有两种选择（0或1），最高会达到2n的时间复杂度，但针对一些题目，可以依靠某些限定条件，大幅降低时间复杂度，从而变相达到既优化了空间也优化了时间的目的。
【注：相关位运算内容在此不作说明】
举例
（一）吃奶酪
链接：P1433 吃奶酪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意：房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。
分析：据题意可将其抽象为，从原点出发，返回走过所有点的最小距离。最值问题容易想到搜索。搜索时跳过重复路径，最后进行比较即可。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace ConsoleApp1 7 { 8 internal class Program 9 { 10 static int n; 11 static double res = double.MaxValue; 12 static NodeToNode[][] ntn; 13 static int[] vis; 14 static void Main(string[] args) 15 { 16 Program p = new Program(); 17 n = int.Parse(Console.ReadLine()); 18 n += 1; 19 double[] x = new double[n], y = new double[n]; 20 x[0] = 0; 21 y[0] = 0; 22 for (int i = 1; i < n; i++) 23 { 24 string[] inp = Console.ReadLine().Split(' '); 25 x[i] = double.Parse(inp[0]); 26 y[i] = double.Parse(inp[1]); 27 }//录入所有点，包括（0，0） 28 ntn = new NodeToNode[n][]; 29 for (int i = 0; i < n; i++) ntn[i] = new NodeToNode[n]; 30 for (int i = 0; i < n; i++) 31 { 32 for (int j = 0; j < n; j++) 33 { 34 ntn[i][j].dis = Dis(x[i], y[i], x[j], y[j]);//计算每两个点间的距离并编号 35 ntn[i][j].next = j; 36 } 37 ntn[i] = ntn[i].OrderBy(k => k.dis).ThenBy(k => k.next).ToArray();//一定要注意这个排序方式！！！！！ 38 } 39 40 //for (int i = 0; i < n; i++) 41 // for (int j = 0; j < n; j++) 42 // Console.WriteLine(ntn[i][j].dis + " " + ntn[i][j].next); 43 44 vis = new int[n]; 45 vis[0] = 1; 46 p.Dfs(0, 0.0, 1); 47 Console.WriteLine(res.ToString("0.00")); 48 //Console.ReadLine(); 49 } 50 public void Dfs(int cur, double sum, int cnt) 51 { 52 if(cnt == n) 53 { 54 res = res <= sum ? res : sum; 55 return; 56 } 57 if (sum >= res) return; 58 for(int i = 0; i < n; i++) 59 { 60 if(vis[ntn[cur][i].next] == 0 && cur != ntn[cur][i].next) 61 { 62 vis[ntn[cur][i].next] = 1; 63 Dfs(ntn[cur][i].next, sum + ntn[cur][i].dis, cnt + 1); 64 vis[ntn[cur][i].next] = 0; 65 } 66 } 67 } 68 public struct NodeToNode 69 { 70 public double dis; 71 public int next; 72 } 73 private static double Dis(double x1, double y1, double x2, double y2) 74 { 75 return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 76 } 77 } 78 }
这种思路本质上是对除原点以外的所有点，进行全排列，比较每一种排列结果，其时间复杂度为O(N*N!)，（应该是），在比赛中一般仅能承受N<=10的数据范围。
再分析：因为在深度搜索中会出现大量重复访问的数据，所以优化搜索算法，最先想到的一般是记忆化处理，记住到达某一个点的最小距离。但这种方法不能保证最坏的情况，有一部分情况和之前无异。本题除了距离因素，就只剩奶酪因素，既然记住距离还不够，那就只能在“奶酪”上下手了。
对于每个奶酪，只有两种情况：吃过/没吃过；抽象出来即，对于每个点：走过/没走过。发现对于每个事物（奶酪/点），仅有两种状态（访问过/没访问过），满足基本状态压缩的前提，所以我们考虑使用二进制来表示每个状态。
a. 大化小：最终问题是让总距离最小，最终距离是基于每一次选择得来的，那么就把从一个点到一个新的点，这一选择视为一个子问题。并且每次选择总以最小最小距离为基础进行操作，每次选择处理方式相同。
b. 分情况定变量：对于每个点，只有两种情况（走或不走）；我们需要知道当前这个点是否走过，所以要记录当前所在点；还需要知道已经走过了几个奶酪，所以要记录对点（奶酪）的访问情况，共两个变量。用f[i][j]表示老鼠当前走到第i个点（奶酪）处，且走过的点的二进制状态为j时，最短的距离。
如：可以使用二进制10100110来表示已经走过第2、3、6、8个奶酪（定义此处索引从1开始），此时j的值为166。需要注意的是，第i个状态是从低位向高位的第i位，即从低位向高位进行转移。
c. 推方程：如果要走这个点（保证该点可访问）那么f[i][j] = f[j][k - (1 << (i − 1)] + dis(i, j)其中f[i][j]表示以i为起点走成状态j的最小距离，dis表示两点间距离。
【解释 k - (1 << i − 1) 】
（1） 符号‘<<’：表示某十进制数对应的二进制数向右移，等价于对十进制数*2。
如：1 << 3表示将1对应的二进制编码向右移动4位 (1)10 = (0001)2 右移5位变为（1000）2 = （8）10 = 1 * 23
（2）式子：最终目标的状态 – 当前位置的状态 = 中间状态
如：（5）10 =（0101）2 = (0111)10 – (0010)2 = (7)10 - （2）10
上一个中间状态 = 目标状态 – 当前位置状态
【难点】为什么可以用 k & (1 << (i – 1)判断合法位置
我们设一个状态 k = 01101，表示第一、三、四列（从低位开始）中的某个点已经访问过；
由于我们是一行一行访问的，所以在k状态我们应该访问第三行的点了，那第三行我们应该访问哪个点，或者说状态k由哪些状态转移而来呢？
状态k(01101)由三种状态（必然是前两行的状态）来的：
前两行在三、四列已访问，第三行只好访问第一列；(01100)
前两行在一、四列已访问，第三行只好访问第三列；(01001)
前两行在一、三列已访问，第三行只好访问第四列；(00101)
无非就是这三种情况，现在我们来考虑怎么来表示状态s由这三种状态来的，k & (1 << (i - 1))就是用来实现这个功能的，即判断当前情况是否为其上一个情况转移而来。
for (int i = 1; i <= 4; i++) 01101 & (1<<0) = 01101 & 1 = 00001 01101 & (1<<1) = 01101 & 10 = 00000 01101 & (1<<2) = 01101 & 100 = 00100 01101 & (1<<3) = 01101 & 1000 = 01000 01101 & (1<<4) = 01101 & 10000 = 00000
由此得出，只有和k=01101有1重合结果才大于0，根据这个特性判断此列是否可以访问。
d. 定边界：本题在搜索过程中不存在索引非法而导致的无法访问点，但需要对初值进行设定，因为其默认值为0，我们需要存储最小距离，所以应对初值设定为一个较大的值。
【注：文末代码中已附有更加详细的注释】
（二）01背包
【注：题目解析请转至该文章有关动态规划 - PaperHammer - 博客园 (cnblogs.com)】
在该问题中，对于每种物品只有两种选择，放与不放，故也可以使用状态压缩进行优化。
如：有5件物品，
如果这5件物品都不放的话，那就是00000;
如果这5件物品都放的话，那就是11111;
观察可知，在上面的例子中00000 ~ 11111可以代表所有的情况，转化为十进制就是0到(1 << (5 – 1));
其中，所以f[10000]只能从f[00000] + W[1] 转移过来；f[11000]可以从f[01000] + W[1]或者f[10000] + W[2]转移过来,以此类推
总结
1. 注意位运算的运算等级顺序，括号很重要
2. 状压dp的特点一般是规模比较小，一般小于15，最多不超过20；而且一般只有两种决策
状态压缩比较难理解，本篇文章也花了快两周时间，虽然写成了笔记，但本人理解程度依旧不深，在此希望与各位大佬相互交流一起学习
【感谢您可以抽出时间阅读到这里；受限于水平，内容可能会有许多不妥之处，许多地方可能存在错误，还请各位大佬留言指正，请见谅，谢谢！】
#附文中所提到的第一题的代码 及 状压模板
（1）吃奶酪
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace ConsoleApp1 7 { 8 internal class Program 9 { 10 static int n,sum; 11 static double res = double.MaxValue; 12 static double[][] f; 13 static double[] x, y; 14 static void Main(string[] arg) 15 { 16 n = int.Parse(Console.ReadLine()); 17 x = new double[n + 1]; 18 y = new double[n + 1]; 19 20 for (int i = 1; i <= n; i++) 21 { 22 string[] inp = Console.ReadLine().Split(' '); 23 x[i] = double.Parse(inp[0]); 24 y[i] = double.Parse(inp[1]); 25 } 26 27 //初始化，因为之后的比较是取较小的一个，所以将所有值预设为最大 28 f = new double[n + 1][]; 29 for(int i = 1; i <= n; i++) 30 { 31 f[i] = new double[(1 << n)]; 32 Array.Fill(f[i], double.MaxValue); 33 } 34 35 DP(f, n); 36 Console.WriteLine(res.ToString("0.00")); 37 //Console.ReadLine(); 38 } 39 static public double DP(double[][] f, int n) 40 { 41 //分别枚举所有可能的二进制状态、当前点所在的位置和能在当前状态下到达当前点的位置。 42 43 //【枚举状态】 44 for (int k = 1; k <= (1 << n) - 1; k++)// k表示下一个位置所代表的状态【减1是因为长度为(1 << n)，索引是从0到(1 << n) - 1] 45 { 46 //【枚举起点】 47 for (int i = 1; i <= n; i++)// i表示当前位置 48 { 49 if ((k & (1 << (i - 1))) == 0)// 此情况下非合法的中间情况【减1是因为索引上限】 50 continue; 51 if (k == (1 << (i - 1)))// 两状态相同， 即为同一个点 52 { 53 f[i][k] = 0;// 同一个点，距离为0 54 continue; 55 } 56 //【枚举中间点】注：中间点点不等于起点，中间点指从i到终点之间的点 57 for (int j = 1; j <= n; j++)// j => k - (1 << (i - 1)) 58 { 59 if ((k & (1 << (j - 1))) == 0 || i == j)// 如果 不合法 或 中间点等于起点 则跳过 60 continue; 61 f[i][k] = Math.Min(f[i][k], f[j][k - (1 << (i - 1))] + Dis(i, j)); 62 } 63 sum += k ^ (1 << (i - 1)); 64 Console.Write(sum + " "); 65 } 66 sum = 0; 67 Console.WriteLine(); 68 } 69 for (int i = 1; i <= n; i++) 70 { 71 double cur = f[i][(1 << n) - 1] + Dis(i, 0); 72 res = Math.Min(res, cur); 73 } 74 return res; 75 } 76 private static double Dis(int a,int b) 77 { 78 return Math.Sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])); 79 } 80 } 81 }
（2）一般状压模板
1 int n; 2 int maxn = 1 << n;//总状态数。 3 //枚举已有的集合数。按照状态转移的顺序，一般从小编号到大编号。 4 for(int i = 1; i <= m; ++ i){ 5 //枚举当前集合中的状态。 6 for(int j = 0; j < maxn; ++ j){ 7 //判断当前集合是否处于合法状态，通常我们需用一个数组提前处理好。如g数组; 8 if(当前状态是否合格){ 9 for(int k = 0; k < maxn; ++ k){ 10 //枚举上一个集合的状态。 11 if(上一个集合的状态是否合格 + 上一个集合的状态和当前状态的集合是否产生了冲突){ 12 列写状态转移方程。 13 } 14 } 15 } 16 } 17 } 18 }