DP的引入

DP为什么比暴力快:因为它舍弃了冗余信息,只关心答案是多少,不关心是怎么来的。

无后效性

只要求出了f(n),怎么求出f(n)就无所谓了,未来与过去无关,这就叫做无后效性

严格定义:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

最优子结构性质

在求出小问题的最优解之后,就可以利用它们求出大问题的最优解。大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”。

DP的条件

  • 能将大问题拆成性质相同的小问题
  • 状态满足无后效性
  • 满足最优子结构性质

例题:DAG最短路

给定一个DAG,求S到T的最短路

满足无后效性:到了一个点,就无所谓怎么来的了

满足最优子结构性:对于一点P,只关心最小费用f(P),并用其推后面的问题

f(P)为到达P点所需的最小费用,R为有路通向P的所有点,w_{R\rightarrow P}RP的过路费,则:

f(P)=\min{f(R)+w_{R\rightarrow P}}

DP的本质

为什么会快

无论DP还是暴力,目标都是在可能解空间中找到最优解。暴力做法是枚举所有的可能解,但DP是枚举有希望成为答案的

DP自带剪枝,直接舍弃了一大堆不可能称为最优解的答案,而暴力是将所有都考虑进去

DP的核心思想就是尽量缩小可能解空间

操作过程

大事化小,小事化了

将大问题分解为一个个小问题,然后求解这些小问题,最终得到大问题的解

设计DP算法、

首先将面对的局面表示为x,这一步称为设计状态

对于状态x,记该状态的答案为f(x),即要求出的答案为f(T)

然后找出状态x与哪些状态有关联,写出一个式子(动态转移方程),然后通过f(p)来求出f(x)

设计流程:设计状态,表示局面,然后设计转移

例题

最大子段和

P1115,求一段序列中连续且非空的最大子段和

由于连续,所以要么继承上一个,要么重新开一个,设f(n)1n的最大子段和,序列为{a},则有

f(x)=\max(f(x-1)+a_x,a_x)

然后从头到尾统计最大f(x)即可

最长不下降子序列(LIS)

求一段序列中最长不下降子序列的长度

f(x)为以a_x结尾的LIS的长度,那么答案就是\max{f(x)}

状态转移方程:

f(x)=\max\limits_{p<x, a_p\leq a_x}{f(p)}+1

算法复杂度为O(n^2),使用优化可以O(n\log n)

记忆化搜索

记忆化搜索就是将已经计算过的且可能会被再使用的状态记录下来,防止时间的浪费。例如求斐波那契数列的第n项,有

\begin{cases}
f(0)=0\
f(1)=1\
f(n)=f(n-1)+f(n-2)\quad(n>1)
\end{cases}

如果单纯的写递归计算f(x),那么有可能一个f被计算过很多次,这样浪费时间,将其存下来的话会节省很多时间

计数类DP

P1255数楼梯

f(x)=f(x-1)+f(x-2),又是一个斐波那契的递推

注意开高精度

P1002过河卒

\begin{cases}
f(mx,my)=0\quad(mx,my)\text{为马的位置及马的控制点}\
f(i,j)=\max[f(i,j),f(i-1,j)+f(i,j-1)]
\end{cases}

最后修改日期:2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。