个人dp小结

发布于 2018-10-01  133 次阅读


前言:最近做了很多动态规划题,但是每次遇到新的题目的时候还是做不出来,于是就像做一个小结,梳理下近些天做的题目,从中获取经验。

第零节:DP的基础概念

动态规划和其他某些算法具有一定的相似度,都是利用问题的可划分性以及子问题的相似性来进行归纳,降低时间复杂度。
来说说动态规划的几个基本条件:

条件 解释
无后效性 已求解的子问题不受后续阶段的影响\(^{[1]}\)
最优子结构 下一个阶段的最优解应该能够由前面各阶段子问题的最优解导出
子问题重叠 动态规划通过对每个子问题只解一次,把解保存在一个需要时就可以查看的表中\(^{[2]}\)

[1]:在《算法竞赛进阶指南》中有一个很好的说法,“动态规划对状态空间的遍历构成一张有向无环图,遍历顺序就是该图的一个拓扑序。”
[2]:其实就是动态规划会用查询的方式解决重复出现的子问题,而不是像递归那样每次算一遍。

构成动态规划的三要素:

要素 解释
状态 即我们通常所说的f或dp数组,他们用来表示什么
阶段 即各个状态在不同时刻的表示
决策 状态如何转移到 下一个状态

知道了这些并没有什么用,重要的还是在题目中体会。

第一节:线性DP

我们在解决一些线性区间上的最优化问题的时候,往往也能够利用到动态规划的思想,这种问题可以叫做线性dp。
- [x] 线性空间

在有关线性dp问题中,有着几个比较经典而基础的模型,例如最长上升子序列(LIS)、最长公共子序列(LCS)、最大子序列和等,那么首先我们从这几个经典的问题出发开始对线性dp的探索。

>注:下表引用自《算法竞赛进阶指南》P258表

LIS问题

问题描述 最长上升子序列。给定一个长度为\(N\)的数列\(A\),求数值单调递增的子序列的长度是多少。\(A\)的任意子序列\(B\)可表示为\(B=\{A_{k1},A_{k2},...,A_{kp}\}\),其中\(k_1
阶段划分 子序列的位置(数列[latex]A\)中的位置,从前到后)
转移方程 $$F[i]=max{F[j]+1},0\le j< i, A [ j ] < A[i] $$
边界 \( F[0]=0 \)
目标 \(max\{F[i]\},1\le i \le N\)

还有两个大家自行看书~(打这个太累啦)
通过这三个问题,我们可以了解到,线性DP无论是多维还是一维,“线性”都体现在“作用在空间上的递推”————DP的阶段沿着各个维度线性增长,从一个或多个“边界点”开始有方向地向整个状态空间转移、扩展,最后每个状态上都保留了以自身为目标子问题的最优解。
下面我们开始线性DP的进阶,我们从例题开始。

【例1】Mr. Young's Picture Permutations\(^{poj2279}\)

这是一个五维的线性DP,从该题给出的解法中我们发现,设计动态规划的状态转移方程,不一定要以“如何计算出一个状态”的形式给出,也可以考虑“一个已知状态应该更新哪些后续阶段的未知状态”。

第二节:背包

其实我们OIer很多时候都是靠眼睛学习的,偶尔通过听觉也是不错的。

⭐0/1背包

⭐完全背包

⭐多重背包

⭐分组背包

区间DP

树形DP

⭐背包类树形DP

推荐个视频


哇,你居然发现了这里!