闫氏dp分析法

用于求有限集中的最值。方法:依次考虑,层层递进,将每一个条件从1开始考虑,再将每一种情况用数组的方式保存结果。那么当条件增加到2的时候就可以通过在条件为1的时候所保存的数据作为参考,得到条件为2时的最佳结果。

闰式DP分析法:https://www.bilibili.com/video/BV1X741127ZM?share_source=copy_web

背包九讲:https://www.bilibili.com/video/BV1qt411Z7nE?share_source=copy_web

一.背包问题

01背包问题:每件物品最多只能用一次

i个物品选还是不选

完全背包问题:每件物品有无限个

i个物品选几个(可选0个)

多重背包问题(优化):每件物品个数可能不同

i个物品选还是不选(数量限制)

分组背包问题:物品有N组,每个物品有若干个

i物品选哪个

二.线性DP

线性dp往往指在一个序列上进行的dp,当然也可能有两个甚至多个序列。

一般来讲,线性dp的三个步骤分别有以下特点:

设计状态:至少有一维表示当前考虑的对象在数列上的位置。

状态转移:必须找到这条线上前面的位置的dp值来推出当前位置的dp值。

边界条件:第一个位置单独讨论。

数字三角形(入门必备)

最长上升子序列

最长公共子序列

三.区间DP

概念

区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态 表示将下标位置 到 的所有元素合并能获得的价值的最大值,那么 , 为将这两组元素合并起来的代价。

区间 DP 的特点:

合并 :即将两个或多个部分进行整合,当然也可以反过来;

特征 :能将问题分解为能两两合并的形式;

求解 :对整个问题设最优值,枚举合并点,将问题分解为左右两个部分,最后合并两个部分的最优值得到原问题的最优值。

例题

石子合并

四.计数类DP

整数划分

五.计数位统计DP

六.状态压缩DP

最后修改:2022 年 01 月 25 日
如果觉得我的文章对你有用,请随意赞赏