DP学习笔记

# 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