闫氏DP分析法
dp的本质: 有限集中的最值问题
两个阶段
-
化零为整,状态表示(
f[i]) 利用集合减少枚举的个数 1.1 集合是什么 1.2 属性是什么min/max/count -
化整为零,状态计算 将f[i]划分成多个子集,然后利用子集的结果整理出
f[i]的值 2.1 不重复(求数量时不重复,求最大(小)的时候可以重复(比如RMQ问题)) 2.2 不遗漏(必须满足)
划分依据:寻找最后一个不同点
多做题
四个例题
01背包
状态表示
1
2
3
第一维一般是前几个,后续的维度一般是限制
集合:前i个物品且总体积不超过V的选法的集合
属性:集合当中方案的最大价值
状态计算
1
2
3
4
5
对应的是集合的划分
最后一个不同点:选不选第i个物品
f[i][j]代表的集合 = 所有 不选i且总体积不超过V的方案 ∪ 所有选i且总体积不超过V的方案
故
f[i][j] = max(max(所有 不选i且总体积不超过V的方案) ∪ max(所有选i的方案))
