.
二进制状态压缩动态规划
对于某些情况，如果题目中所给的限制数目比较小，我们可以尝试状态压缩动态规划。例如，题目中给出数据范围(n<=20),这个一般情况下是一个状压DP的提示。
状态压缩，顾名思义，要把每种状态压缩起来。一个经典的问题是洛谷P1171,也就是著名的货郎担问题，它是一个NPC难题,目前不存在多项式算法。当题目中(n)的范围比较小时，我们可以考虑使用状态压缩动态规划(状压DP)来解决。(注：本文出现的"状压DP"若无特殊说明，均指状态压缩动态规划)
我们用状压DP解决货郎担问题的时间复杂度是(O(n^{2}2^{n})),我们用(dp[i][j])来表示目前处在第(i)个城市，集合(j)中的城市已经全部都经过一次所花费的最小代价。那么，由于(j)的范围是(2^{n})(每个城市都有两种状态，共(n)个城市)，而(i)的取值范围是(n),所以一共有(2^{n}n)种状态，每种状态可以出发去其他任何一个城市，所以有(n)种决策，所以总时间复杂度为(O(n^{2}2^{n}))。
通常，我们使用状压DP的时候，把集合用一个(int)型整数表示，它通常取值为([0,2^{n}-1])，用来表示每个元素的两种状态，从而表示出当前状态。我们怎么知道元素(i)是否在这个集合中呢？我们可以用1<<i-1来表示，这种表示方法可以查出得到元素(i)所代表的那一位，然后我们就可以用位运算符(&)来于集合取一个交集，如果返回为真，那么说明元素(i)在原集合中，否则不在。
状态剪枝
普通的动态规划通常有很多个状态，而这些状态会占用大量内存以及消耗时间。有的时候，我们没必要真的去计算每一个状态，因为有的状态永远也无法转移到答案。
我们结合一道例题具体分析.
显然，我们有一个思路：用(f[i][j])来表示我们在岛屿上(i)处，我们上一次跳跃距离是(j),那么我们就可以很方便的转移了，时间复杂度(O(n^2))，空间复杂度(n^2)。
现在，出题人想卡掉这种做法。这种做法的复杂之处在于：有一些状态，我们永远也无法访问，但我们还是记录并从他向外界转移了。这不是我们希望的，而我们观察到有用的(j)只存在于一定范围内。这个发现可以让我们减少自己的决策数，实际上，打表发现，有用的(j)的分布只存在于([1,sqrt{n}])中，所以我们可以进一步优化到(O(nsqrt{n})).
这种优化实际上是一种直觉，我们看到(n)的范围是(10000),我们必须想办法优化，DP优化的一般思路是:打表->发现规律->利用规律->AC.
** 改变DP对象**
这道题，如果(H,W<3000),那么我们可以很方便的用一般的(2D)状态的DP来做。时间复杂度(O(H*W)) __ , 但是这道题的H,W太大了，我们只好考虑别的方法。
我们观察到，不能走的点很少，只有(2000)个，我们打算从他入手。
我们把所有的不能走的点，把(x)作为第一关键字，(y)作为第二关键字，进行排序,同时我们让点((H,W))也加进来，显然他会排在最后一个。
现在，我们用(dp[i])表示到达第(i)个不能走的点的路径条数（假设第i个格子可以走），注意到我们是根据横纵坐标递增排序的，所以对于两个数(i,j) 如果(i<j)那么一定无法从(j)到达(i),这确保了无后效性。
我们考虑两个点((X_1,Y_1),(X_2,Y_2)),如果中间不含任何无法走的方块，那么一共有(frac{(X_2-X_1+Y_2-Y_1-2)!}{(X_2-X_1+1)!(Y_2-Y_1+1)!})种方法。
我们用(W[x][y])表示(x->y)的路径条数，也就是上面那个式子，我们可以通过预处理阶乘的方法，那么对于每个(W)我们可以O(1)求，但是(W[0][n+1])并不是答案，因为经过了不能走的点。
考虑如何计算(dp[i])，对于没有任何限制，那么它为(W[0][i]),我们考虑，如果第一个遇到的不可走的点为(j),那么接下来走到(i)的方案数为(dp[j]*W[j][i]),我们把这个数从中减去就好啦！答案存在(dp[n+1])中。
差分dp
对于这个题，我们不是太好设定状态呢。我们首先先给所有的物品排序，按照价格从小到大。那么，我们可以把他们放在数轴上，作为数轴上的点。
每个集合就是一条线段咯！而我们要求的值，就是每条线段的长度之和。因为，最左边的是价值最低的，最右边的是价值最高的。那么，我们可以这么设计状态。
(dp[i][j][k])表示，当前已经放置了(i)个商品，也就是有(i)个点都已经属于某条线段了，还有(j)条线段只有一个端点的方案数，那么，我们每次更新一个点，都会对(k)产生一点贡献，这个贡献是多少呢？(j*(a_i-a_{i-1})).为什么是(j)乘呢？我们每次不是只放在了一组里吗？原因是，如果每次只更新单租的贡献，那么状态不好转移。我们不知道这一组之前上一个是谁。
也就是说，我们每次一个点更新以后，就把将来一定会用到的值更新。因为我们是已经排好序了，所以这么做是没问题的。
那么，每个状态(dp[i][j][k])都有以下几个转移方式转移而来：
1.我们让商品(i)开一条线段，那么(dp[i][j+1][k+j*(a_i-a_{i-1})]+=dp[i-1][j][k])
2.我们让(i)单独成一组，那么(dp[i][j][k+j*(a_i-a_{i-1})]+=dp[i-1][j][k])
3.我们让(i)结束一条线段,此时须保证(j!=0)，那么(dp[i][j-1][k+j*(a_i-a_{i-1})]+=dp[i-1][j][k]*j)
4.我们把(i)加入到某一条线段里(但不结束这条线段)，那么(dp[i][j][k+j*(a_i-a_{i-1})]+=dp[i-1][j][k]*j)
最终答案存在(sum_{i=0}^{k}dp[n][0][i])
连通块dp
文文也不知道该怎么给这种dp取名，目前还没遇到过这样的题目。
例题：
给出(n)个数字(a_1...a_n),以及一个整数(L),(n<=100,a_i<=1000,L<=1000),求有多少种排列，满足(|a_1-a_2|+|a_3-a_4|+....+|a_{n-1}-a_n|<=L).
这道题我们很难直接设状态，我们先把他们排一遍，然后把他们一个一个加入到排列中。每加一次，都统计一下答案。例如：2,7,?,5,6,?,?,?,?,9
还没有填数的地方用?来表示，假设我们已经把前(i-1)个数全部填进去了，现在考虑第(i)个，由于是排好序的，第(i)个一定大于其中任意一个.
我们用(dp[i][j][k][l])来表示当：
填入数字个数为(i),连通块个数为(j),当前的代价为(k),连通块结尾是否已经全部填充（l=0 没有， l=1一部分 l=2 全部填充）的方案总数
小细节：
1.每填入一个元素，都要更新答案的值为新造成的差值的绝对值乘上连通块的个数(因为连通块是等价的，可以调换位置)
2.每个元素，要么合并两个连通块，要么新建一个连通块，要么插在某个连通块开头或结尾
转移方式结合在代码中详细解释
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
ll dp[101][101][1001][3];
ll a[101];
const ll MOD = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n, l;
cin>>n>>l;
for(int i = 0; i < n; i++)
{
cin>>a[i];
}
sort(a, a + n);
if(n == 1) //特殊情况
{
cout << 1;
return 0;
}
a[n] = 10000; //无穷大
if(a[1] - a[0] <= l) dp[1][1][a[1] - a[0]][1] = 2; //在其中一个终止点填入a[0],还有两个终止点等待填充
if(2*(a[1] - a[0]) <= l) dp[1][1][2*(a[1] - a[0])][0] = 1;
for(int i = 1; i < n; i++)
{
int diff = a[i + 1] - a[i]; //如果i=n-1 diff = inf
for(int j = 1; j <= i; j++)
{
for(int k = 0; k <= l; k++)
{
for(int z = 0; z < 3; z++)
{
if(!dp[i][j][k][z]) continue; //值不存在
//首先尝试填充其中一个端点
if(z < 2 && k + diff*(2*j - z - 1) <= l) //有2j-z-1个位置想要更优(因为这些位置中的某一个将在这一步以后与一个终止点合并)
{
if(i == n - 1)
{
dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] = (dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] + dp[i][j][k][z]*(2-z)*j)%MOD;//我们有j个连通块可以合并
}
else if(z == 0 || j > 1) //i==n-1
{
dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] = (dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] + dp[i][j][k][z]*(2-z)*(j-z))%MOD;//没有连接到结尾
}
if(k + diff*(2*j - z + 1) <= l) //新建连通块
{
dp[i + 1][j + 1][k + diff*(2*j - z + 1)][z + 1] = (dp[i + 1][j + 1][k + diff*(2*j - z + 1)][z + 1] + dp[i][j][k][z]*(2-z))%MOD; //找一个结尾创建
}
}
//接下来填充尾部
//先创建一个新连通块
if(k + diff*(2*j - z + 2) <= l) // 2个新位置可以更新
{
dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z] = (dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z] + dp[i][j][k][z])%MOD;
}
//合到一个连通块中
if(k + diff*(2*j - z) <= l)
{
dp[i + 1][j][k + diff*(2*j - z)][z] = (dp[i + 1][j][k + diff*(2*j - z)][z] + dp[i][j][k][z]*(2*j - z))%MOD;
}
//然后把两个连通块合在一起
if((k + diff*(2*j - z - 2) <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2))
{
if(z == 0)
{
dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*j*(j-1))%MOD; //j*P2种可能的合并
}
if(z == 1)
{
dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*(j-1)*(j-1))%MOD; // (j-1)P2+(j-1) 种可能的合并
}
if(z == 2)
{
if(i == n - 1)
{
dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z])%MOD;//一种可能的合并，直接继承过来
}
else
{
dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*(j-2)*(j-1))%MOD;// (j-2)P2 + 2(j-2)种可能的合并
}
}
}
}
}
}
}
ll answer = 0;
for(int i = 0; i <= l; i++)
{
answer = (answer + dp[n][1][i][2])%MOD;
}
cout << answer << '
';
return 0;
}
常见的DP技巧还有很多，文文这里仅举5例，难度依次递增。
由于文文水平不足，难免存在错误或纰漏，欢迎指正。
有更多技巧想要和文文探讨，可以QQ(434935191)或邮箱(v@18sec.cn)联系文文。