Voldemort's blog

Voldemort's blog

我好菜啊

DP学习笔记

posted on 2020-07-30 10:00:52 | under 笔记 |

X01

动态规划,简称dp,大概是从一个初始的最优状态,每一步都进行最优决策,最终得到最优结果的过程。——GZW
其实DP的本质是状态定义。——GZW
DP的代码是很简单的,所以我们讲题的时候只讲思路,不敲代码。——GZW

X02——简单dp

搞懂上面GZW神仙的名言之后,我们来看题。
Q1:数字三角形

给定一个高为 $n$ 的数字三角形,每一个数字都代表一个权值,求从顶开始,每一次只能向下货右下移动法人最大权值。

这题显而易见是 DP……
我们定义状态 $f(i,j)$ 表示走到点 $(i,j)$ 时得到的最大值,则这个状态只能由点 $(i-1,j)$ 和 $(i-1,j-1)$ 得到,所以推出转移方程:
$$F_{i,j}=\max (F_{i-1,j},F_{i-1,j-1}+a_{i,j})$$
所以怎么这么像记忆化搜索呢?
没错,就是很像,而且时间复杂度两者相同!
所以我还是去打记忆化搜索吧。——TRZ

Q2:最长上升子序列

给定一串数字 $a_1,a_2,\dots a_n$,求它的最长上升子序列的长度

我们定义状态 $f(i)$ 表示区间 $[1,i]$ 中最长上升子序列的长度,则 $f(i)$ 可以从 $f(k)$ ( $1 \le k < i$) 得到,为了取得最大值,所以对所有的可行状态取最大值,得到转移方程:
$$f(i)=\max f(k)+1,1\le k<i$$

X03——背包dp

先咕着……

X04——分组dp

分组类的dp主要是这么问你的:

给定一组序列,要求把序列分成 $m$ 组,求你能获得的收益最大或者最小。

我们定义 $f(i,j)$ 表示把 $i$ 个数字分成 $j$ 组所获得的最大(小)收益,则IAKIOI