状压DP（超详细）⼀、定义总述状态压缩动态规划，就是我们俗称的状压DP，是利⽤计算机⼆进制的性质来描述状态的⼀种DP⽅式。
很多棋盘问题都运⽤到了状压，同时，状压也很经常和BFS及DP连⽤。
状压dp其实就是将状态压缩成2进制来保存其特征就是看起来有点像搜索，每个格⼦的状态只有1或0 ，是另⼀类⾮常典型的动态规划举个例⼦：有⼀个⼤⼩为n*n的农⽥，我们可以在任意处种⽥，现在来描述⼀下某⼀⾏的某种状态：设n = 9；有⼆进制数 100011011（九位），每⼀位表⽰该农⽥是否被占⽤，1表⽰⽤了，0表⽰没⽤，这样⼀种状态就被我们表⽰出来了：见下表所以我们最多只需要 2^（n + 1） - 1的⼗进制数就好（⼆进制形式是n个1）现在我们有了表⽰状态的⽅法，但⼼⾥也会有些不安:上⾯⽤⼗进制表⽰⼆进制的数，枚举了全部的状态，DP起来复杂度岂不是很⼤？没错，状压其实是⼀种很暴⼒的算法，因为他需要遍历每个状态，所以将会出现2^n的情况数量，不过这并不代表这种⽅法不适⽤：⼀些题⽬可以依照题意，排除不合法的⽅案，使⼀⾏的总⽅案数⼤⼤减少从⽽减少枚举为了更好的理解状压dp，⾸先介绍位运算相关的知识。
1. ’&’符号，x&y，会将两个⼗进制数在⼆进制下进⾏与运算(都1为1，其余为0）然后返回其⼗进制下的值。
例如3(11)&2(10)=2(10)。
2. ’|’符号，x|y，会将两个⼗进制数在⼆进制下进⾏或运算（都0为0，其余为1）然后返回其⼗进制下的值。
例如3(11)|2(10)=3(11)。
3. ’^’符号，x^y，会将两个⼗进制数在⼆进制下进⾏异或运算（不同为1，其余为0）然后返回其⼗进制下的值。
例如3(11)^2(10)=1(01)。
4. ’~’符号，~x，按位取反。
例如~101=010。
5. ’<<’符号，左移操作，x<<2，将x在⼆进制下的每⼀位向左移动两位，最右边⽤0填充，x<<2相当于让x乘以4。
状态压缩Abstract信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。
然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。
Keywords状态压缩、Hash、动态规划、递推ContentIntroducti o n作为OIers，我们不同程度地知道各式各样的算法。
这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为原数的一半)、平衡树，有的以)运行，例如二级索引、块状链表，再往上有O(n)、O(n p log q n)……大部分问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为P (deterministic Polynomial-time)类问题，例如在有向图中求最短路径。
然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法，NPC(NP-Complete)和NPH(NP-Hard)就是其中的两类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的Traveling Salesman Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题尚不知有多项式时间的算法存在。
P和NPC都是NP(Non-deterministic Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类问题都可以在多项式时间内归约到NPC问题中去。
NPH包含了NPC和其他一些不属于NP(也更难)的问题，NPC问题的函数版本(相对于判定性版本)一般是NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是NPH的。
1. 资源问题1-----机器分配问题总公司拥有高效生产设备M台，准备分给下属的N个公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。
其中M<=15，N<=10。
分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。
数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。
接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。
用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。
则状态转移方程为:F[I,j]:=max(f[i-1,k]+w[i,j-k])2. 资源问题2------01背包问题有N件物品和一个容量为V的背包。
第i件物品的费用是c，价值是w。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3. 线性动态规划1-----朴素最长非降子序列设有由n个不相同的整数组成的数列，记为:a(1)，a(2)，……，a(n)且a(i)<>a(j) (i<>j)例如3，18，7，14，10，12，23，41，16，24。
若存在i1且有a(i1)则称为长度为e的不下降序列。
如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。
程序要求，当原数列给出之后，求出最长的不下降序列。
F[i]:=max{f[j]+1}4. 剖分问题1-----石子合并在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，由文件读入堆数N及每堆的石子数（≤２０）。
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5. 剖分问题2-----多边形剖分多边形三角剖分是计算几何的一个几何基元.它可以简化问题规模,在计算机图形学、模式识别和地理数据库方面有重要应用.F[I,j]:=min(f[j,k]+f[k,j]+a[k]*a[j]*a[i]);6. 剖分问题3------乘积最大今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。
维特比算法例题维特比（Viterbi）算法是一种动态规划算法，常用于隐马尔可夫模型（HMM）中的路径搜索问题。
以下是一个简单的维特比算法的例子：假设有一个简单的HMM，包含两个状态（状态1和状态2），以及两个观测序列（观测1和观测2）。
状态转移概率如下：P(状态1→状态1) = 0.7P(状态1→状态2) = 0.3P(状态2→状态1) = 0.4P(状态2→状态2) = 0.6观测概率如下：P(观测1|状态1) = 0.5P(观测1|状态2) = 0.5P(观测2|状态1) = 0.4P(观测2|状态2) = 0.6现在我们要找出最有可能的状态序列，使得观测序列的概率最大。
首先，我们需要计算每个状态在每个时刻的概率。
这可以通过以下公式计算：P(状态i, t) = P(观测t|状态i) * P(状态i, t-1)其中，P(观测t|状态i)是观测概率，P(状态i, t-1)是上一个时刻的状态概率。
然后，我们需要找出最有可能的状态序列。
这可以通过以下公式计算：P(最优, t) = max P(状态i, t) * P(状态i→状态j)其中，P(最优, t)是在时刻t的最有可能的状态概率，P(状态i, t)是在时刻t的状态i的概率，P(状态i→状态j)是从状态i转移到状态j的概率。
最后，我们可以通过回溯算法找出最有可能的状态序列。
回溯算法是一种通过逐步回溯搜索树来找出最有可能的解的算法。
具体来说，我们从最后一个时刻开始向前回溯，找出最有可能的状态，然后继续向前回溯，直到找到最有可能的初始状态。
以上是一个简单的维特比算法的例子，希望能帮助您理解该算法的基本原理和应用。
