状态dp主要分为两种类型
- 基于连通性的状态压缩dp (棋盘问题)
- 基于集合类的状态压缩dp (全排列问题,组合问题)
棋盘问题
即有一个二维的棋盘空间,该类状态压缩dp是基于在这个二维空间的情况之下的
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| 291.蒙德里安的梦想 | 给定一个NxM的棋盘,用1x2的小方块填满有几种方案 | 逆向,结论,受到前一行影响 | 题解 |
| 1064.小国王/互不侵犯 | 在nxn的棋盘上放置m个国王,国王会攻击四周8个位置 | 棋盘dp,分析 | 题解 |
| 327.玉米田 | 在nxm的土地上种植,且不能种在贫瘠土地,且不能种在相邻土地,求所有种法 | 二进制存储土地信息 | 题解 |
| 292.炮兵阵地 | 在nxm的棋盘上摆,且只能摆在平地,上下左右不能相邻摆的最多炮兵数 | 同时记录当前,前驱状态 滚动数组 | 题解 |
| nc1.冒险公社 | 给出一个预测结果,根据预测结果判断是否成立,并求出最多的绿岛数 | 线性dp,记录前驱状态 | 题解 |
集合类(全排列,组合)
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| 91.最短Hamilton路径 | 起点为0,终点为n-1,要经过0~n-1,求他们的最短路径 | 状态dp优化全排列 | 题解 |
| p1441.砝码称重 | 求n个砝码,去掉m个后,能够表示多少个数字 | 布尔01背包,组合问题 | 无题解 |
| p3694.邦邦的大合唱队 | 已知有N个人站成一列,分别属于M个团队,求让每个团队的人都站在一起最小出队次数 | 优化全排列问题+前缀和 | 题解 |
| p3092 | 有N个不同面额的硬币,顺序的付完M个物品,求剩下的最多钱数 | 全排列+二分 | 题解 |
| 524.愤怒的小鸟 | 一共有n只小猪在二维坐标上，每次小鸟发射是抛物线型的,可以击落抛物线上的所有小猪,求最少发射几次小鸟 | 浮点数,预处理,集合类状压 | 题解 |
