什么是动态规划
动态规划通过额外的空间将已经搜索过的相似的结果（指某些具有相同性质解的集合）用一个数组存起来，所以DP中的状态转移看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移！
状态压缩DP
蒙德里安的梦想
典型题例：
求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。
例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。
示例 ：
输入： 输入包含多组测试用例。 每组测试用例占一行，包含两个整数 N 和 M。 当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理 1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0 输出： 1 0 1 2 3 5 144 51205
思路
核心：先放横着得，再放竖着得
总方案数：等于只放横着得小方块得合法方案数。
如何判断当前方案是否合法？
答：所有剩余位置，能否充满竖着得小方块；可以按列来看，每一列内部所有连续得空着的小方块需要偶数个
状态表示：集合集合f[i,j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的状态j的所有方案。（化零为整）
状态计算：集合划分总共有2^n中状态；Σf[i-1,k],其中k为二进制数。（化整为零）
需要注意的是f[i-1,k]要与f[i,j]构成合法的方案，需要满足的条件：
1.j与 k 不能再同一行，即(j & k == 0)
2. 所有的连续空着的位置的长度必须是偶数
边界：f[0,0]=1
答案：f[m,0];
代码：
include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 12, M = 1 << N; //M = 2^n typedef long long LL; int n, m; LL f[N][M]; vector<int> state[M]; //二维数组记录合法状态；写法等价：vector<vector<int>> state(M) bool st[M]; //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。 int main() { while (cin >> n >> m, n || m) { 读入n和m，并且不是两个0即合法输入就继续读入 //预处理，对应满足条件2 for (int i = 0; i < 1 << n; i ++) { int cnt = 0; //记录连续0的个数 bool is_valid = true; //某种状合法（不存在连续奇数个0） for (int j = 0; j < n; j ++) { if ((i >> j) & 1) { //状态i的二进制数的第j位 if (cnt & 1) { //又伸出来的，则看前面连续0的个数是奇数则不合法 is_valid = false; break; } cnt = 0; //前面的是合法的了，计数器可以清零 } else cnt ++; //该位置还是0,增加计数 } if (cnt & 1) is_valid = false; //最后一段判断下是否合法 st[i] = is_valid; //是否合法状体保存再st中 } //预处理，对应满足条件1 for (int i = 0; i < 1 << n; i ++) { state[i].clear(); for (int j = 0; j < 1 << n; j ++) if ((i & j) == 0 && st[i | j]) state[i].push_back(j); } //dp开始 memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 1; i <= m; i ++) for (int j = 0; j < 1 << n; j ++) //遍历第i列所有状态 for (auto k : state[j]) //遍历i-1列状态k,合法转移 f[i][j] += f[i - 1][k]; cout << f[m][0] << endl; } return 0; }
树形DP问题
没有上司的舞会
典型题例：
Ural 大学有 N 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
示例 ：
输入： 第一行一个整数 N。 接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。 接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。。 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 输出： 5
思路
等价于完全背包问题：有一个容量为n的背包，且有n个物品，对应的体积分别为1~n,恰好装满背包的方案数
状态表示：集合f[u,0]表示所有从以u为根得子树中选择，并且不选择u这个点得方案
集合f[u,1]表示所有从以 u 为根得子树中选择，并且选择u这个点得方案
状态计算：f[u,0] += Σ max(f[si,0]+f[si,1]) 其中si表示父节点u得每个孩子节点
f[u,1] = Σ f[si,0] 父节点选了，孩子节点就不能选了
答案为两个集合的最大值
代码：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 6010; int n; int enjoy[N]; int h[N], e[N], ne[N], idx; //邻接表 bool has_father[N]; //是否有父节点 int f[N][N]; int add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } void dfs(int u) { f[u][1] = enjoy[u]; //选择u则先加上u的高姓度 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); //两个集合的求法 f[u][0] += max(f[j][0], f[j][1]); f[u][1] += f[j][0]; } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++) scanf("%d", &enjoy[i]); memset(h, -1, sizeof h); for (int i = 1; i < n; i ++) { int x, y; scanf("%d%d", &x, &y); has_father[x] = true; //y是x的father add(y, x); } int root = 1; while (has_father[root]) root ++; //找到root节点 dfs(root); printf("%d\n", max(f[root][0], f[root][1])); return 0; }
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
