25.4.10

闫氏dp分析法(从集合角度分析dp问题)

干瞪眼看做题只是自设难度,多动手列(哪怕很简单)辅助思考才能简化而做题(如列竖式)

所有dp问题都是有限集中的最值问题

可能状态为指数级别,因而要用dp去优化,最优化.

为什么可以优化?

一般分析要经过两个阶段:

1.化零为整

状态表示f[i](一般都必须做过类似的题目才会好想出来)

划归,不是一个一个去枚举,而是一堆一堆去枚举,再去细化.把一堆有相似点(所有满足相同限制条件)的元素划为一个子集,然后用某一个状态来表示

  • 维度表示一个或一类东西(集合)的一种限制条件
  • f[i]的值表示属性(最值,数量等)

2.化整为零

状态计算

把f[i]划分成若干个子集(不重(可能)不漏(必须))来求

划分依据:寻找最后一个不同点

例题

01背包