Today is the fifth day of the course.

Note:

dp是什么?

动态规划(DP)不是某种具体算法,而是一种思想。
核心在于:把大问题转化为小问题,利用小问题的解,推断出大问题的解。

什么是状态?

例子

《硬币问题》

Luogu-B3635

今天你手上有无限的面值为1,5,11 元的硬币。
给定n,问:至少用多少枚硬币,可以恰好凑出n 元?

思考
用f[x]表示多少钱的时候最小的硬币数,f[x]由上一次选择的最小硬币数+1得到,所以我们只需要找到上一次选择的硬币+1的最小值就可以了。故有状态转移方程:

$$ f(x)=\left\{ \begin{aligned} 1+f[x-1]\newline 1+f[x-5]\newline 1+f[x-11]\newline \end{aligned} \right. $$

《凑字》

现在有一篇文章是一个字,你可以添加一个字或者复制整个文章再粘贴(即字数翻倍)。说人话就是可以使一个数字加1或者×2

求码出n字的最小次数

数组f[x],x表示码出x字所需的最小增加次数,因为x字要么是加以得来,要么是×2得来。

所以如果x是奇数,那么他的次数为:

$$ f[x]=f[x-1]+1 $$

如果x是偶数,那么他可能是+1得到的,也可能是×2得到的,所以有:

$$ f[x]=min(f[x-1],f[x/2])+1 $$

所以状态转移方程为:

$$ f[x]= \begin{cases} f[x]=f[x-1]+1 & \{x|x=2n+1,n∈Z\}\newline f[x]=min(f[x-1],f[x/2])+1 & \{x|x=2n, n∈Z\} \end{cases} $$

初步总结:状态

硬币问题中,要表达“我们需要凑出n 元钱”这个局面,可以设计状态:“f[x] 表示凑出x 元用的最少硬币数”。
上楼梯问题中,设计状态:“f[x] 表示走上x 级的方案数”。

可见,只有大问题和小问题拥有相同的形式,才能考虑拆分子问题。
如果满足这个要求,那么我们遇到的每个子问题,都可以通过某种简洁的形式来表达。
我们把可能遇到的每种“局面”称为状态。

所以最优解的最优解就是我们要的结果,一层层下去到可以人工计算或者无需计算的开头,这就是DP

形象的说,状态就是格子,而寻找状态就是寻找格子,dp就是用之前的格子来推出之后的格子。

转移

例子

LIS(最长上升子序列)

给定一个数组a,求a中最长的上升子序列

最长上升子序列:数组中最长的那一个单调上升的子序列。

下文我们以lis指代最长上升子序列。

数组f[x]表示以a[x]结尾的lis,a[p]表示接到的数,即为小于a[x]的数。所以我们只需要把a[x]接到每一个f[p]的后即可找到lis。

所以只要a,p满足p<x,a[p]<a[x],然后枚举f[p]+1的最大值就是f[x]的最优解。

此时我们已经找到了状态以及状态转移方程:

$$ \begin{equation} f[x]=\mathop{\max}_{p<x,a[p]<a[x]} \{ f[p]+1 \} \end{equation} $$

小结:状态和转移

一个dp题,应该经历2个过程:

  1. 设计状态。把面临的每一个问题,表达成一个个「状态」。
  2. 设计转移。写出状态转移方程,从而利用小问题的解推出大问题的解。

可以通俗的说:大事化小,小事化了

dp的两种实现方式

dp的递推形式可以从过去推到现在,也可以从现在推到未来,时间复杂度和空间都是一样的,只是写法不同罢了,就像dp可以用递推实现也可以用记忆化搜索实现。

可以称为“我从哪里来”和“我到哪里去”

刚刚的《硬币问题》也可以使用“我到哪里去”实现:

$$ f[x] \to f[x+1]\\ \to f[x+5]\\ \to f[x+11] $$

《Lis》问题也可以:

$$ f[x] \xrightarrow[p>x]{a[p]>a[x]} f[p] $$

小结:设计转移

我从哪里来:对于一个没有求出解的状态,利用能走到它的状态,来得出它的解。

我到哪里去:对于一个已经求好了解的状态,拿去更新它能走到的状态。

两者只有写法上的区别,没有效率上的区别(根据状态和状态转移方程来选择写法)

dp总结

dp可以分为3步:

  1. 设计状态
  2. 找到状态转移方程
  3. 在“我从哪里来”和“我到哪里去”中选择好写的一个实现代码

完成后你就完美的切掉了一道dp题,congratulations !

dp与贪心的区别

通过一个例题来说明:

你手上有1 个苹果,他每次施法可以让苹果数量+1 或×2。
请问你至少需要多少次施法,才能恰好得到n 个苹果。

和刚刚的《凑字》问题是一模一样的,dp:

$$ f[x]= \begin{cases} f[x]=f[x-1]+1 & \{x|x=2n+1,n∈Z\}\newline f[x]=min(f[x-1],f[x/2])+1 & \{x|x=2n, n∈Z\} \end{cases} $$

而贪心要好写一些:

$$ f[x]= \begin{cases} f[x]=f[x-1]+1 & \{x|x=2n+1,n∈Z\}\newline f[x]=f[x/2]+1 & \{x|x=2n, n∈Z\} \end{cases} $$

可以看到,贪心是直接使用了f[x/2]+1而不去确认是否有更优解,贪心是对当前状态下的最优解而不是全局最优解,所以人们说贪心是“目光短浅”的。但是对于这道题,贪心更快也更好些。而dp开头讲过,dp是把大问题转化为小问题,利用小问题的解,推断出大问题的解。

这便是dp与贪心的区别,他们之间没有目前的分界线,可能一道题贪心和dp都占了。

贪心算法和动态规划最大的不同在于:贪心法并不是首先寻找子问题的最优解,然后在其中进行选择,而是首先做出一次「贪心」选择——在当时(局部)看来最优的选择,然后求解选出的子问题,从而不必费心求解所有可能相关的子问题。

—— 《算法导论》

欢迎查看第二部分哦。

This article was written on July 21, 2022 at 13:41.