DP笔记 2021.2.4 上午
Preview
-
我们先不对动态规划做一些枯燥的定义。
-
而是看两个简单的问题，看看如何分析和解决这样的问题，从这几道题的分析过程共同点或者说特点中，归纳总结出动态规划的一般特点和思路。
-
然后再通过几道例题来强化理解我们总结的动态规划做题思路。
-
之后我们将从另一角度理解动态规划，即记忆化搜索视角。
-
我们还将理解DP一种简单情况的转移路径，DAG上的DP。
-
再通过大家独立思考，实践两道题目，实现对dp算法的初步运用。
填满网格
给出一个 \(2*n\) 的网格, 你现在需要用 \(n\) 个 \(2*1\) 的多米诺骨牌占满整个棋盘.
多米诺骨牌可以横着或者竖着放.
求有多少方案数占满整个棋盘.
\(N \leq 10^6\)
设 \(f_n\) 为 \(n\) 列的答案, 则根据如何对最后一两列放多米诺分情况讨论可得
\[f_n = f_{n-1} + f_{n-2} \]这是递推, 也算是一个简单的dp, 只不过绝大多数dp的转移方程不是根据这题一样简简单单的一个加号就解决的.
补充
矩阵快速幂可以将其优化成 \(O(logn)\)
网格图路径计数
给出一个 \(n*m\) 的网格, 每次只能向右或者向下走, 求从 \((1,1)\) 走到 \((n,m)\) 的方案数, 其中有些位置是不能走的.
\(n, m \leq 1000\)
如果没有障碍物: 设 \(dp_{i, j}\) 表示从 \((1, 1)\), 走到 \((i, j)\) 的方案数.
考虑上一步从哪里走过来可得
\[dp[i][j]=dp[i-1][j]+dp[i][j-1]. \]答案就是 \(dp_{n, m}\)
对于障碍：如果 \((i,j)\) 是一个障碍，则定义 \(dp_{i,j} = 0\)
dp[1][1]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (s[i][j]=='.')
{
if (i==1&&j==1) continue;
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
}
走金字塔的最大价值路径
给出一个高度为 \(n\) 的金字塔，你现在要从金字塔的顶端走到金字塔的底端
金字塔的第 \(i\) 层，第 \(j\) 房间 (记为 \((i, j)\)) 有价值为 \(a_{i, j}\)的宝藏，每一步能从 \((i, j)\) 能走到, \((i+1, j)\) , \((i+1, j+1)\) 求从金字塔顶部走到底部能获得的最大的价值是多少?
和前面两题差不多, 只不过前面是求方案数, 运算法则为加法, 而这里求最优值, 运算法则是取 max
设 \(dp_{i, j}\) 表示从塔顶走到 \((i, j)\) 能得到的最大的价值是多少, 则:
\[dp_{i, j} = max(dp_{i-1, j-1}, dp_{i-1, j})+a_{i, j} \]dp[1][1]=a[1][1];
for (int i=2;i<=n;i++) {
for (int j=1;j动态规划的基本思想——最优化
利用最优化原理把多阶段过程转化为一系列单阶段问题, 利用各阶段之间的关系, 逐个求解.
更具体的, 假设我们可以计算出小问题的最优解, 那么我们凭借此可以推出大问题的最优解, 进而我们又可以推出更大问题的最优解 (要满足最优子结构)
从小问题答案推到大问题的答案
而最小的问题也就是边界情况我们可以直接计算出答案来.
基本思想是将待求解的问题分解为若干个子问题 (阶段), 按顺序求解子阶段, 小的子问题的解, 为更大子问题的求解提供了有用的信息.
由于动态规划解决的问题多数有重叠子问题这个特点, 为减少重复计算, 对每一个子问题只解一次.
就像刚刚那几个递推式我们如果递归来做就会有很多冗余的计算.
动态规划的状态
动态规划过程中, 需要有状态表示和最优化值 (方案值)
状态表示是对当前子问题的解的局面集合的一种 (充分的) 描述.
最优化值 (方案值) 则是对应的状态集合下的最优化信息 (方案值), 我们最终能通过其直接或间接得到答案.
对于状态的表示, 要满足三条性质:
-
具有最优化子结构: 即问题的最优解能有效地从问题的子问题的最优解构造而来
-
具有简洁性: 尽可能的简化状态的表示, 获得更优的时间复杂度.
-
同时能够全面的描述一个局面. 一个局面有一个答案, 而这个局面是需要一些参数来描述的.
设计状态的关键就是: 充分描述, 尽量简洁.
动态规划的精髓——状态转移
由于具有最优化子结构 (在最优化问题种), 所以求当前状态的最优值可以通过其他的 (较小的问题) 状态的最优值加以变化而求出. 所以, 当一个状态的所有子结构都已经被计算之后, 我们就可以通过一个过程计算出他的最优值, 这个过程就是状态的转移.
- 注意：状态的转移需要满足要考虑到所有可能性.
计算动态规划的时间复杂度
\[简单动态规划时间复杂度==状态数×状态转移复杂度. \]同时也就引出了 DP 的两种优化时间的方法:
-
减少状态的维数
-
加速状态转移, 例如数据结构优化或者分析性质
最长上升子序列
给出一个长度为 \(n\) 的数列 \(a_{1...n}\), 求这个数列的最长上升子序列.
就是给你一个序列, 请你在其中求出一段不断严格上升的子序列, 子序列是不一定要求连续的.
\(0 < n <= 1000\)
这是一道最为经典的完全用动态规划来解决的问题.
设 \(dp_i\) 为以 \(a_i\) 为末尾的最长上升子序列的长度.
最后的答案就是我枚举一下最长上升子序列的结束位置, 然后取一个最大值即可.
问题是如何求这个数组?
那我们回过头来想一想最开始说的动态规划的基本思想, 从小的问题推出大的问题.
假设我们知道了 \(dp_{1...i-1}\), 我们怎么才能根据这些信息推出来 \(dp_{i}\).
再次强化一下定义: \(dp_i\) 表示以 \(i\) 结尾的最长上升子序列。
我们只需要枚举这个上升子序列倒数第二个数是什么就好了.
\[dp_i = max(dp_j) + 1\ (a_j < a_i, j < i) \]在这个问题的分析中, 突破口?
-
设计出了 \(dp_{1...n}\) 这个可以储存以 \(i\) 结尾的子序列中最优的答案, 这个状态表示.
-
通过分析问题成功能将当前状态的最优值能过由之前状态转移出来.
-
套上之前的公式: 状态数×状态转移复杂度.
-
状态数: \(dp_{1...n}\), 只有n个状态.
-
状态转移: 由于你每次都需要枚举之前的所有数, 所以单次转移是 \(O(n)\)
-
所以总复杂度 \(O(n^2)\)
for (int i=1;i<=n;i++) {
dp[i]=1;
for (int j=1;jdp[i] ) dp[i]=dp[j]+1;
}
Luogu P1091 合唱队形
\(N\) 位同学站成一排, 音乐老师要请其中的 \(N?K\) 位同学出列，使得剩下的 \(K\) 位同学排成合唱队形.
合唱队形是指这样的一种队形: 设 \(K\) 位同学从左到右依次编号为 \(1,2,...\), 他们的身高分别为 \(T_1,T_2,...,T_K\)
则他们的身高满足 \(T_1
你的任务是, 已知所有N位同学的身高, 计算最少需要几位同学出列, 可以使得剩下的同学排成合唱队形.
\(n<=100000\)
我们设 \(f_i\) 表示以 \(i\) 结尾的最长上升子序列长度.
我们设 \(g_i\) 表示以 \(i\) 开头的最长下降子序列长度.
然后我们枚举哪一个为中心的最高点, \(f_i+g_i-1\) 取最大值即可.
Luogu P1018 乘积最大
设有一个长度为 \(N\) 的数字串, 要求选手使用 \(K\) 个乘号将它分成 \(K+1\) 个部分, 找出一种分法, 使得这 \(K+1\) 个部分的乘积能够为最大.
\(6
用 \(f_{i, a}\) 表示前 \(i\) 位数包含 \(a\) 个乘号所能达到的最大乘积, 我们只需要枚举上一个乘号所在的位置即可.
将 \(j\) 从 \(a\) 到 \(i - 1\) 进行一次枚举, 表示前 \(j\) 位中含有 \(a-1\) 个乘号, 且最后一个乘号的位置在 \(j\) 处. 那么当最后一个乘号在 \(j\) 处时最大值为前 \(j\) 位中含有 \(a - 1\) 个乘号的最大值乘上 \(j\) 处之后到 \(i\) 的数字.
\[f_{i, a} = max(f_{i, a},\ f_{j, a-1} * cut_{j + 1,i}) \]\(cut_{b + 1, i}\) 表示 \(b + 1\) 到 \(i\) 位数字
然后再写个高精度即可
\[f_{i, j} = f_{i, j}\\ \]提示
基本上一般简单的 DP 题, 就是先想想状态, 然后再看能不能转移, 如果不能转移, 换种设状态的方式, 或者增加一下状态的维数, 使得局面描述的更加详细.
最长公共子序列
给定两个字符串 \(S\) 和 \(T\), 长度分别为 \(n\) 和 \(m\), 求解这两个字符串的最长公共子序列 (Longest Common Sequence)
\(n,m<=1000\)
我们设 \(f_{i, j}\) 表示, \(S\) 串的第 \(i\) 个前缀和 \(T\) 串的第 \(j\) 个前缀的最长公共子序列.
分情况:
-
如果 \(S_i == T_j\), \(f_{i, j} = f_{i-1, j-1} +1\)
-
如果 \(S_i != T_j\)，\(f_{i, j} = max(f_{i-1, j},f_{i, j-1})\)
-
最后答案就是 \(f_{n, m}\)
\(O(nm)\)
思路从何而来?
可用动态规划求解的问题, 一般有两个特征:
-
最优子结构 (全局最优一定是子问题最优结合而得)
-
重叠子问题 (也就是如果是原先搜索的话要有不少冗余的计算, 通过 DP 我们每一个状态就计算一次, 减少了复杂度, 记忆话搜索本质是一样的)
本质来说我们就是要想办法把问题化小.
转移分支正确性证明
对于 \(f_{i, j}\), 如果, 两个串最后一个位置相同, 这两个位置一定在公共子序列中.
那么我们只需要求出 \(S\) 的 \(i-1\) 前缀和 \(T\) 的 \(j-1\) 前缀的最长上升子序列就可以了, 而这个就是把问题化小.
如果最后一个位置不相同, 那么两个位置一定不能匹配, 所以肯定是另外两种情况选最大的.
\(f_{i - 1, j}, f_{i, j - 1}\) 顶多比 \(f_{i, j}\) 大 \(1\), 所以 \(S_i == T_i\) 时, \(f_{i, j} = f_{i - 1, j - 1} + 1\) 一定不会使答案比\(max(f_{i - 1, j}, f_{i, j - 1})\)更差
最长公共上升子序列 LCIS
给两个序列 \(A\) 长度为 \(n\) 和 \(B\) 长度为 \(m\), 求最长的公共子序列, 还要保证这个序列是上升的.
其实这是一类套路, 只不过这种套路可以考场上自己推出来, 而不是由他人教. 当然有些套路, 比如网络流 Dinic 算法怎么写, 这个自己推就费劲了. 但是这题是完全可以自己研究出来的.
\(O(n^2m^2)\)
\[f_{i, j} = max(f_{k, l}) + 1\\ (a_i == b_j > a_k == b_l, k < i, l < j) \]\(O(nm^2)\)
\[g_j = max(f_{k, j})\ (k < i)\\ f_{i, j} = max(g_{l})\ (a_i == b_j > b_l, l < j) \]\(O(nm)\)
我们设 \(f_{i,j}\) 表示 \(A\) 前 \(i\) 个位置和 \(B\) 前 \(j\) 个位置所能产生的最长公共上升子序列的长度. 其中 \(a_i == b_j\), 也就是最后这个位置是匹配的. 若是 \(a_j != b_j\) 则对应函数值为 \(0\).
我们从1到n枚举i计算 DP 值, 在枚举i的过程中维护 \(g_k=max(f_{1...(i-1), k})\)
然后 \(f_{i, j}=max(g_k) ( k
总复杂度 \(O(n*m)\)
\[g_j = max(f_{k, j})\ (k < i)\\ h = max(g_l)\ (b_l < a_i, l < j)\\ f_{i, j} = h + 1\ (a_i == b_j) \]for (int i=1;i<=n;i++) {
int tmp=0;
for (int j=1;j<=m;j++)
if (a[i]==b[j]) {
dp[i][j]=tmp+1;
f[j]=max(f[j], tmp+1) ;
//其实不用取max，肯定是更大的对吧
} else if (a[i]>b[j])
tmp=max(tmp,f[j]);
}
网格图路径计数
给出一个 \(n*m\) 的网格, 每次只能向右或者向下走, 求从 \((1,1)\) 走到 \(n,m\) 的方案数, 其中有些位置是不能走的.
\(n,m \leq 1000\)
我们用搜索算法来计算答案, 然而搜索的时间复杂度是指数级的, 观察一下: 这是有些重复计算的.
我们发现在这个 DFS 的过程中, DFS 出来的值只与带入参数，也就是 \((x,y)\) 有关, 而不同的 \((x,y)\) 有 \(N*M\) 个. 而我们之前搜索的问题在于有大量的重复计算, 多次调用同一个 \((x,y)\), 每次都从新计算.
有一个很直观的想法就是, 第一次调用的时候就把答案记下来, 之后调用不重新算, 直接返回之前已经计算出的答案即可. 这就是记忆化搜索.
int DFS(int x,int y) {
if (dp[x][y]==-1)
return 0;
if (x==n&&y==m)
return 1;
if (dp[x][y]!=-1)
return dp[x][y];
int ans=0;
if (x滑雪
给定一个区域, 由一个二维数组给出. 数组的 \((i,j)\) 代表点 \((i,j)\) 的高度. 我们要找一个最长的滑雪路径, 注意滑雪只能从高往低处滑.
\(f_{x, y}\) 存储在当前位置下山的最大长度, 它等于它旁边的 (上下左右) 比它矮的山的 DP 值加 \(1\) 的最大值, 即
\[f_{i, j} = max(f_{i - 1, j}, f_{i, j - 1}, f_{i + 1, j}, f_{i, j + 1}) \]要保证对应的高度小于 \(H_{x, y}\) 才能取 max.
一般递推式动态规划还要注意枚举状态的顺序, 要保证算当前状态时子状态都已经算完了.
但是记忆化搜索不需要, 因为记忆化搜索就是个搜索, 只不过把重复的部分记下来了而已. 我们不用像递推一样过于关注顺序, 像搜索一样直接要求什么, 调用什么就好.
int dfs( int X,int y) {
if(dp[x][y]!=-1)
return dp[x][y];
int i,j;
dp[x][y]=1;
if(x> 1&&h[x-1][y]1&&h[x][y-1] 记忆化搜索
在有一些 DP 问题中, 状态之间的转移顺序不是那么确定, 并不能像一些简单问题一样写几个 for 循环就解决了.
我们可以直接计算最终要求的状态, 然后在求这个状态的过程中, 要调用哪个子状态就直接调用即可, 但是每一个状态调用一遍之后就存下来答案, 下次计算的时候就直接取答案即可, 就不需要从新再计算一遍.
虽然看上去每一次都计算不少, 但是因为每一个状态都计算一次, 所以均摊下来, 复杂度 = 状态数 * 状态转移.
拓扑图的dp
拓扑图dp通常是在拓扑图上求关于所有路径的某种信息之和. 当然这里的 “和” 的运算法则可以是加法或是取 max 和 min. 或者其他定义的运算.
按拓扑序沿着有向边转移就可以了.
BZOJ4562 食物链
给定 \(n\) 个点 \(m\) 条边的有向无环食物网, 求其中有多少条极长食物链.
\(n<=10^5\), \(m<=2*10^5\)
拓扑图 DP 经典题
设 \(f_u\) 为以节点 \(u\) 为终点的食物链数量.
\[f_u = \sum_{v, u \in E} f_v \]按照拓扑序的顺序转移即可.
上面的式子是求一个点时, 枚举其所有入边转移, 具体写代码的时候, 我们一般就只记出边再记录一个入边太麻烦了. 所以我们一般不枚举入边, 而是枚举出边从每个点往后更新, 也就是在上面的式子中, 我们对于每个 \(v\) 向后进行更新, 枚举 \(v\) 出边指向的所有 \(u\) 点, 然后 \(f_u += f_v\)
其实我们对于一般非有关期望和概率的 DP, 如果题目中每一个转移关系是双边的, 那么如果我们把 DP 的每一个状态记为一个点, DP 状态之间关系构成的图就是一个拓扑图.
拓扑图 DP 实际上就是已经给了我们这个拓扑关系了, 也就不需要我们自己找了, 其实是更简单.
经典题
给一个 \(n\) 个点 \(m\) 条边的无向图, 每一条边 \((u,v)\) 有两个参数 \((len, cnt)\) 表示边的长度以及边上不同的礼物数量，我们在每一个走过的边 \((u, v, len, cnt)\) 只能选 \(1\) 个礼物, 选择的方案数是 \(cnt\).
我们现在想从 \(S\) 走到 \(T\), 我们想要求出在只走最短路径的情况下有多少种选择的礼物的方案数.
一条路径选择礼物的方案数就是每条边的 \(cnt\) 的乘积. 答案对一个大质数取模.
\(n<= 100000\), \(m<=300000\)
\((u,v,len,cnt)\) 其实就是 \((u,v)\) 点对有 \(cnt\) 条长度 \(len\) 为边, 求 \(S\) 到 \(T\) 的最短路径方案数.
求以最短路径为前提的一些问题, 果断先建最短路图.
毕竟, 最短路图建出来是一个 DAG, 而 DAG 就比随意的图具有更好的性质, 不求白不求.
然后就是求 DAG 上从 \(S\) 到 \(T\), 路径的方案数.
设 \(f_u\) 为从 \(u\) 到 \(T\) 路径的方案数:
\[f_u= \sum_{edge(u,v,cnt)} f_v*cnt \]答案就是 \(f_S\)
拓扑排序的写法上一题中讲过了, 我们这次来介绍记忆化搜索的实现方法.
初始直接调用dfs(S)即可
int dfs(int u) {
if (u==T)
return 1;
if (f[u]!=-1)
return f[u];
f[u]=0;
for (int i=hd[u];i;i=pr[i]) {
dfs(to[i]);
f[u]=((long long)f[to[i]]*cnt[i]+f[u]) % mod;
}
return f[u];
}