1、从集合角度考虑DP问题(闫氏DP分析法)框架
DP
(1)状态表示
(a)集合
(a.1)所有选法
(a.2)条件
(b)属性：常用的有Max , Min , Count;
(2)状态计算 -> 划分集合
(保证不重不漏，不重不一定要满足，比如取Max)
把状态分成2个子集，这两个子集元素是已知的
计算当前状态
并且80%都是根据最后一步不同的操作划分
(3)优化
2、背包问题
有n个物品，和容量为v的背包，每个物品会占vi的容量，有wi的价值，现在让你装的东西总价值最高，问最高的总价值
每个背包问题都是由此问题变形
01背包
题目：https://www.acwing.com/problem/content/2/
最大特点：每个物品只能用一次
DP
(1)状态表示 f[i][j]
(a)集合
(a.1)条件
(a.2.1) 从前i个物品选
(a.2.2)总体积 <= j;
(b)属性：Max
(2)状态计算
把f[i][j]的选法划分成包含i，不包含i
不包含i的最大值：限制1 - i , <= j , 不包含i -> 1 - i-1,<= j
那么最大值就是f[i - 1][j]
包含i的最大值
限制：1-i , <= j , 包含i
由于这里都包含第i个物品，所以把他去掉后最大值的编号仍然不变
利用这个思想我们的限制就变成了
1 - i - 1 , <= j - vi
那他就是f[i - 1][j - vi]
但是注意前面我们把i去掉了，所以要加回来，就是
f[i - 1][j - vi] + wi;
这两边最大值算出来了就把他们取max就是f[i][j]
f[i][j] = max(f[i-1][j] , f[i-1][j-vi]+wi);
(3)优化
我们可以发现第1维只用到了i和i - 1可以滚动数组，还可以把第一维直接删除，但是这样会有问题
因为我们从小往大枚举，所以f[j-vi]在第i层的时候更新了，导致不是第i - 1层的j - vi;
于是我们可以从大往小枚举，这样j - vi在第i层还没有更新过，
此时的j - vi就是i - 1层的
https://www.acwing.com/activity/content/code/content/9444462/
完全背包
题目：https://www.acwing.com/problem/content/3/
最大特点：每个物品可以无限用
DP
(1)状态表示f[i][j]
(a)集合
(a.1)条件
(a.2.1) 从前i个物品选
(a.2.2)总体积 <= j;
(b)属性：Max
(2)状态计算
把f[i][j]划分成选0个，选1个的最优解，选2个的最优解…选k个的最优解
选0个就是f[i - 1][j],和01背包一样
然后假设现在选了k个，我们仍然可以用刚才”曲线救国”的方法
只是数量变成了k个
f[i][j] = max(f[i-1][j],f[i-1][j-kvi]+kwi)
(3)优化
我们观察次序关系
f[i][j] =
max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w);
f[i][j-v] =
max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w);
然后惊奇的发现f[i][j]要取Max的每一项只比f[i][j-v]多w，根据我们前面曲线救国的原理，我们最后加w，最大值序号任然不变
在最后的时候加w就可以了
f[i][j] = max( f[i-1][j],f[i][j-vi]+wi );
然后这个方程还可以用前面的方法优化空间，但是我们要求的是第i层而不是i - 1 , 所以从小到大枚举
https://www.acwing.com/activity/content/code/content/9446082/
多重背包
题目：https://www.acwing.com/problem/content/4/
加强版：https://www.acwing.com/problem/content/5/
最大特点：每种物品限制拿si个
朴素版和朴素完全背包一模一样，只是要判断目前是否拿的数量超过了限制就行，其他的和完全背包分析一模一样
f[i][j] = max(f[i-1][j - vi * k] + wi * k)
k = 0 , 1 , 2 , … , si;
朴素版https://www.acwing.com/activity/content/code/content/9446799/
(3)优化(针对加强版的方法)
不能用完全背包的方法优化，因为有si的限制
我们可以把si拆分成log si个组，以便快速求解
这样我们就把件数条件消除，最终用01背包求解
具体怎么做/合法性
首先一个数都是可以用比他小的2^x的数凑出来，因为每个数都能用二进制表现出来
一般情况
s = 200，分成： 1,2,4,8,16,32,64,73
因为我们从低往高找2^k很方便，只不过会有余数，其中这个73就是200 - (1+2+4+8+16+32+64) = 200 - 127;
合法性
1,2,4,8,......,2^k , C( C < 2^(k+1) );
1-2^k可以凑出0-2^(k+1)-1 , 加上C,就能凑出C-s;
由于C < 2^(k+1) , 因此0-2^(k+1)-1 并 c-s一定是0-s;
由于我们是取Max，所以重复了也没关系
加强版
https://www.acwing.com/activity/content/code/content/9448588/
分组背包
题目：https://www.acwing.com/problem/content/9/
最大特点：每一组里只能选1个
我们只需要在01背包基础上再枚举一个k，表示选s[i]组的哪一个物品就可以了
https://www.acwing.com/activity/content/code/content/9448688/
3、线性DP
所有递推的顺序有一个模糊的线性的顺序就是线性DP
经典题目：数字三角形
https://www.acwing.com/problem/content/900/
DP
(1)状态表示f[i][j]
(a)集合：所有从起点，走到(i,j)的路径
(b)属性：Max
(2)状态计算
把f[i][j]划分成从来自左上方，和来自右上方
来自左上：我们任然可以用曲线救国的方法，就是计算f[i][j]时，先写出从起点到左上方的最大值再加上a[i][j]就可以了
因为反正每条路径的终点都是a[i][j]和里面都有a[i][j]
右上：与左上同理
f[i][j] = max ( f[i-1][j]+a[i][j] , f[i-1][j-1] + a[i][j] );
DP的时间复杂度一般是状态数量*转移数量
O(500^2 * 2)
https://www.acwing.com/activity/content/code/content/9451909/
经典题目：最长上升子序列
https://www.acwing.com/problem/content/897/
DP
(1)状态表示f[i]
(a)集合：以第i个数结尾的上升子序列
(b)属性：Max;
(2)状态计算
把f[i]分成上一个是第0,1,2,…,i-1个数，我们把任意其中一个称作j，但是这些不一定都存在，因为要求上升
由于我们从前往后遍历，所以f[j]已经知道了，那从f[j]转移来的最长上升子序列就是f[j]+1(因为i也是1个数)
f[i] = max ( f[i] , f[j] + 1 ),j = 0,1,2,…,i-1;
时间：O(n^2)
https://www.acwing.com/activity/content/code/content/9452066/
经典题目：最长上升子序列||
https://www.acwing.com/problem/content/897/
(3)优化(贪心 + 二分)
从样例中发现一点性质，我们发现我们不需要存3,因为如果可以接到3的后面，就可接到1的后面，并且1的使用范围大
受此启发，我们可以存每种长度的最长上升子序列的结尾的值最小是多少,设他为f[i]
并且f数组一定单调递增，这一点很显然
步骤
如果a[i] > f[i]就把ai加到fi的末尾，长度加1
否则找出第一个比ai大的数f[tmp] , 把f[tmp]替换成ai;
因为末尾的数越小后面能加的数越多
并且这样的操作是能保证f接着单调递增，因为
首先ai <= f[tmp] < f[tmp + 1] , 所以f[tmp + 1]没问题
然后f[tmp - 1] < ai , 所以f[tmp - 1]没问题
https://www.acwing.com/activity/content/code/content/9453605/
经典题目：最长公共子序列
https://www.acwing.com/problem/content/899/
DP
(1)状态表示f[i][j]
(a)集合：a的前i个字母和b的前j个字母能组成的最长公共子序列长度
(b)属性：Max;
(2)状态计算
把f[i][j]划分成这一步00,01,10,11(0表示不选，1表示选)
00：f[i-1][j-1]
11: f[i-1][j-1] + 1;
01和10比较麻烦，不能直接用f[i-1][j],f[i][j-1]表示，回顾定义可知，最后一个字母可能不是以ai或bj结尾的
但是仍然可以用这个表示，因为f[i-1][j]可以表示00或01，并且他表示了最大值，所以这里就表示了00和01的最大值
f[i][j-1]同理，虽然我们发现可能重复，但是求Max重复是没有关系的max(a , b) = a , max(a,b,b) = a;
https://www.acwing.com/activity/content/code/content/9453917/
题目：最短编辑距离
https://www.acwing.com/problem/content/904/
DP
(1)状态表示f[i][j]
(a)集合：所有将a[1-i]变成b[1-j]的操作方式
(b)属性：Min;
(2)状态计算
把f[i][j]划分成这一步删、增、改3个集合
如果是删：那么从a[1 ~ i-1]和b[1-j]匹配，然后由于背包问题曲线救国的原理，可以先求f[i-1][j]后加1
f[i-1][j] + 1;
如果是增：那么a[1 ~ i]和b[1-j]匹配，还是曲线救国
f[i][j-1] + 1;
如果是改：那么a[1 ~ i-1]和b[1 ~ j-1]匹配，那么曲线救国
f[i-1][j-1] + 1;
另外如果ai == bj , 那么就是f[i-1][j-1] +0;
f[i][j] = min ( f[i-1][j] + 1 ,f[i][j-1] + 1 , f[i-1][j-1] + 1)
https://www.acwing.com/activity/content/code/content/9455096/
题目：编辑距离
https://www.acwing.com/problem/content/901/
和上一题基本一模一样，稍微改进代码就能过
https://www.acwing.com/activity/content/code/content/9455163/
4、区间DP
例题：石子合并
https://www.acwing.com/problem/content/284/
DP
(1)状态表示f[i][j]
(a)集合：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式
(b)属性：Min
(2)状态计算
以划分石子的分界线分类
左边1个，右边k - 1个
左边2个，右边k - 2个
…
左边k - 1个，右边1个
用k枚举左边的个数
k = j - i + 1;
f[i][j]划分成1 , 2 , 3 , .... , k - 2 , k - 1;
然后由于曲线救国的原理可以先计算f[i][k] + f[k + 1][j]
最后加上新加的一段pre[j] - prei - 1
题目代码
https://www.acwing.com/activity/content/code/content/9456132/
一般模板
https://www.acwing.com/blog/content/73065/
5、计数类DP
https://www.acwing.com/problem/content/902/
可以把题目看成完全背包，每种物体体积是1-n ， 求必须装满的方案数
DP
(1)状态表示f[i][j]
(a)从1到i中选总体积恰好是j的选法的数量
(b)属性：count
(2)状态计算
把f[i][j]分成第i个物品选了0,1,2,…s个，那方案数就是把这些选法的方案数加起来
选0个i：f[i-1][j] , 1个：f[i-1][j-i]，2个：f[i-1][j-2i]
s个：f[i-1][j-si];
那f[i][j]就是把这些数加起来，但是这样时间复杂度
大约是O( n^2 log n );
我们可以采用和完全背包类似得优化
f[i][j] = f[i-1][j]+f[i-1][j-i]+f[i-1][j-2i]+…;
f[i][j-i] = f[i-1][j-i]+f[i-1][j-2i]+…;
我们发现除了f[i-1][j]其他f[i][j]要算的项都与f[i][j-i]相同，所以
f[i][j] = f[i-1][j] + f[i][j-i];
然后用类似完全背包得方法优化成1维
另一种方法
DP
(1)状态表示f[i][j];
(a)集合：总和是i，并且恰好表示j个数得和得方案
(b)属性：count
(2)状态计算
把f[i][j]分成最小值是1，最小值大于1
最小值是1：f[i-1][j-1],因为f[i][j]里必有一个1，我们把这个1去掉，把和也去掉1，这样于f[i][j]对应;
最小值大于1：f[i-j][j],我们把每个数都减去1，总和就是i-j ,
还是有j个数，这样于f[i][j]对应
f[i][j] = f[i-1][j-1] + f[i-j][j];
https://www.acwing.com/activity/content/code/content/9457610/
6、数位统计DP
https://www.acwing.com/problem/content/340/
count(n , x) 1-n中x出现得次数
那么解是count(b , x) - count(a , x)
然后现在就要求count函数
假设n = abcdefg , 求1在第4位出现得次数
1 <= xxx1yyy <= abcdefg
(1)xxx = 000 - abc-1 , yyy = 000 - 999
ans += abc * 1000;
(2)xxx = abc
(2.1)d < 1 , abc1yyy > abc0efg , ans += 0;
(2.2)d = 1 , yyy = 000 - efg , ans += efg+1;
(2.3)d > 1 , yyy = 000 - 999 , ans += 1000;
ans就是1出现在第4位上的次数，然后用这样的方式就可以做其他的数了
这里有一个问题，就是在第一种情况下如果d = 0 , 那么abc=000时没有实际意义，所以xxx应该从001 - abc
我们不需要去除所有前导0的原因
假设n是5位数，如果我们要找[1,n]区间x出现的个数，如果要去除所有前导0，那么我们只能找出5位数，其他的都找不到
因为x其他位数出现的次数都用前面没有实际意义的前导0完成
https://www.acwing.com/activity/content/code/content/9459114/
7、状压DP
https://www.acwing.com/problem/content/293/
所谓状压DP，就是用二进制数表示状态
此题相当于放小方格，把横向小方格摆完后，竖向是唯一的，所以可以只算横向小方格
用f[i][j]表示第i列，第j个状态的所有方案数，j的二进制位其中一位等于1，表示上一列有横放格子，本列有格子捅出来
转移方程：假设k转移到j是合法的
f[i][j] += f[i-1][k];
注意由状态转移方程式，k状态都是j状态的上1列
因为从k能转移到j，那么所有能转移到k的状态都能转移到j
判断k个状态能否转移到第j个状态
(j & k) == 0//否则就会出现重叠的现象(画图)
j | k没有奇数个连续0，这里k和j的1同时构成了k所在列的方块
k表示了从上一列突出来的，j表示了从第k所在列突出来的
j的二进制下的1，除了有他本来含义，还有就是说明了，他的上一列有一个方块
所以j | k表示了k所在列的方块状态(0表示没有,1表示有)
由于格子规格2*1，并且我们是先横着放的，所以如果有奇数个连续0就会出现什么也放不了的位置
所以要判断j | k没有奇数个连续0
然后这个判断奇数个连续的0可以预处理出来
https://www.acwing.com/activity/content/code/content/9459684/
最短Hamilton路径
https://www.acwing.com/problem/content/93/
DP
(1)状态表示f[i][j]
(a)集合：所有从0走到j走过的所有点是i的路径
(b)属性：Min
(2)状态计算
把f[i][j]用倒数第2个点是谁分类,假设倒数第2个点是k
我们可以求从0到k的长度+从k到j的长度，从k到j的长度已知
然后从0到k中间经过的点是i - (1 << j)
这样我们把i的j的这一位消成了0，就表示不到达j这个点
https://www.acwing.com/activity/content/code/content/9459898/
8、树形DP
https://www.acwing.com/problem/content/287/
DP
(1)状态表示f[u][0] , f[u][1]
(a)集合：所有以u为根的子树中选择，且不选u的方案(0)
所有以u为根的子树中选择，且不选u的方案(1)
(b)属性：Max
(2)状态计算
两个f数组其实已经划分好了状态
如果是f[u][0]，那么可以是加f[son][0]或f[son][1]取Max即可
如果是f[u][1],那么只能是f[son][0];
f[u][0] += max( f[son][0] , f[son][1] );
f[u][1] += f[son][0]
https://www.acwing.com/activity/content/code/content/9460070/
9、记忆化搜索
https://www.acwing.com/problem/content/903/
DP
(1)状态表示f[i][j]
(a)集合：从i , j开始滑的路径
(b)属性：Max;
(2)状态计算
把f[i][j]分割成向上下左右走的集合，就比如说向右走，
我们可以先计算f[i][j + 1]再把他加1，还是曲线救国(小明)
然后这个计算顺序就可以用dfs来实现了，爆搜肯定不行，我们可以用数组f[x][y]存搜的结果
当重复搜x,y点时，我们就可以直接返回f[x][y],不需要重新算
https://www.acwing.com/activity/content/code/content/9460192/
