Loading... 动态规划 <!--more--> ==== ### 动态规划难点 * 意识到这个题用动态规划解决 * 高效设计状态 * 多做题 ### 最长上升子序列问题 * **题目：** （） * 设计状态： * $f\[i\]$表示以$a\[i\]$结尾的最长上升子序列长度。 * 最终答案$max_1\\leq i \\leq n$ * 如何转移？ for(int i=1;i<=n;i++){ f[i]=1; for(int j=1;j<i;j++){ if(a[i]<a[j]) f[i]=max(f[i],1+f[j]); } } * 时间复杂度$O(n^2)$ * 如何优化？ #### 方法一：树状数组优化 * 假设$a_i$互不相同。 * 离散化：$a\_1,a\_2,...,a_n$是一个${1,2,...,n}$的排列 * DP值$f\[i\]$插入数组的$a_i$位置（这里树状数组用于求前缀max） * 离散化？ //a[i]互不相同时 int a[N]; int a2[N]; int ord[N]; int cmp(int i,int j){ return a[i]<a[j]; } void lsh(){ for(int i=0;i<=n;i++){ ord[i]=i; } sort(ord+1,ord+n+1,cmp); for(int i=1;i<=n;i++){ a2[ord[i]]=a[i]; } } * 时间复杂度$O(nlogn)$。 #### 方法二："单调栈" * 令$g\[j\]$表示目前为止，长度为j的上升子序列的末尾元素最小是多少。 * $a\[1...5\]={1,5,2,4,3}$ $g\[1\]=inf$ 插入1，$g\[1\]=1,g\[2\]=inf$ 插入5，$g\[1\]=1,g\[2\]=5,g\[3\]=inf$ 插入2，$g\[1\]=1,g\[2\]=2,g\[3\]=inf$ 插入4，$g\[1\]=1,g\[2\]=2,g\[3\]=4,g\[4\]=inf$ 插入3，$g\[1\]=1,g\[2\]=2,g\[3\]=3,g\[4\]=inf$ * 如何快速更新？ * 二分查找？ * 时间复杂度$O(nlogn)$ * 假如输入数列有重复？ 映射到不同的值上。 #### 例题 * 输入一个整数序列$a\_1,a\_2,...,a_n$，最少需要修改几次使整个序列变成严格上升序列？（要求修改后均为整数）。 * 让$a_i$减去$i$，得到一个数列，求n-该数列最长不下降子序列长度。 ### 最长公共子序列 * 状态：$f\[i\]\[j\]$表示$s\[1..i\],t\[1,,j\]$的最长公共子序列 * 转移方程： $s\[i\]=t\[j\]：f\[i\]\[j\]=f\[i-1\]\[j-1\]+1$ $s\[i\]\\neq t\[j\]：f\[i\]\[j\]=max{f\[i-1\]\[j\],f\[i\]\[j-1\]}$ * 时间复杂度$O(n^2)$ ##### 如果$s,t\\leq100000$呢？ * 保证s中每一个元素出现的次数小于10次。 ###### 思路 * 如果互不相同 * 让t中在s中没有出现过的元素删去，让t以s的顺序排序，算一个最长上升子序列。 * 那次数$\\leq10$呢？ * 转化为LIS（最长上升子序列） * 例如： s=abdbad t=abcbd a:5,1 b:4,2 c:。。 d:6,3 所以t转化为5，1，4，2，4，2，6，3 再求t的最长上升子序列。 * 总结起来就是： 将每个元素在s中出现的下表以降序存在一个链表里，未完。。。 ### DAG上的dp * 输入一个有向无环图（DAG），并给定起点s，边权为正，计算从s到每个点u的最长路长度$d\[u\]$. * 要求时间复杂度$O(n+m)$ * 先进行拓扑排序$v\_1,v\_2...,v\_n$ 假设$v\_1=s$。（否则，s走不到排在s前面的点，可以直接设置它们最短路为-inf） * $d\[v\_i\]=0$ 从$i=2,...,n$，枚举所有指向$v\_i$的边，计算的$d\[v\_i\]=max{d\[v\_j\]+w(v\_j,v\_i)}$ #### 记忆化搜索  ### 背包问题 #### 01背包 * 有$n$个物品，每个有体积$w\[i\]$,价值$v\[i\]$。总体积为$W$的背包最多能装多少总价值？ * $(n,W\\leq2000)$ * 设计状态：$f\[i\]\[j\]$表示$j$体积装前$i$件物品，最大的总价值。 * 如何转移？ $f\[i\]\[j\]=max(f\[i-1\]\[j\],f\[i-1\]\[j-w\[i\]\]+v\[i\])$ `cpp for(int i=1;i<=n;i++){ for(int j=0;j<=w[i];j++) f[i][j]=f[i-1][j]; for(int j=w[i];j<=W;j++){ f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]) } }` 优化空间后： for(int i=1;i<=n;i++){ for(int j=W;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+v[i]) } } #### 完全背包 * 有$n$种物品，每种有体积$w\[i\]$,价值$v\[i\]$且有无限个。总体积为$W$的背包最多能装多少总价值？ * $(n,W\\leq2000)$ `cpp for(int i=1;i<=n;i++){ for(int j=w[i];j<=W;j++){ f[j]=max(f[j],f[j-w[i]]+v[i]) } }` #### 子集和问题 * 有$n$个物品，第$i$个体积为$w_i$。能否选出一个子集和，使总容量为$W$的背包装满？ * $f\[i\]\[j\]=1 or 0$表示用前$i$件物品能否凑出$j$体积。 * $f\[0\]\[0\]=1$ `cpp for(int i=1;i<=n;i++){ for(int j=0;j<=W;j++) f[i][j]=f[i-1][j]; for(int j=w[i];j<=W;j++){ if(f[i-1][j-w[i]]) f[i][j]=1; } } //f[n][W]==1 or 0?` #### 动态子集和问题  #### 01背包 * 有$n$个物品，每个有体积$w\[i\]$,价值$v\[i\]$。总体积为$W$的背包最多能装多少总价值？ * $(n\\leq2000，v\[1\]+v\[2\]+···+v\[n\]\\leq2000,W\\leq10^9)$ * 小技巧：反转状态和dp值 状态$f\[i\]\[v\]$表示前$i$件物品凑出$v$的总价值最小总体积。 边界$f\[0\]\[0\]=0$。 * 伪代码： f[0][0]=0; for(int i=0;i<=n;i++){ f[0][i]=inf; } for(int i=1;i<=n;i++){ for(int j=0;j<=2000;j++){ f[i][j]=f[i-1][j]; } for(int j=0;j<=2000;j++){ f[i][j]=min(f[i][j],f[i-1][j-v[i]]+w[i]); } } ### 区间DP #### 合法子序列问题 * 一个由$$组成的序列，求出最长的合法子序列长度，$(n\\leq300)$。 * 定义：合法子序列是一个合法的括号序列，每一对匹配的括号都是同一类型的。比如$[()\[\]](()())$是合法的。 * 设计状态： $f\[i\]\[j\]$表示在$\[i,j\]$有多长的合法子序列。 * 转移： 如果$a\[l\],a\[r\]$是匹配的括号，则$2+f\[l+1\]\[r-1\]$ 枚举断点$k:f\[l\]\[k\]+f\[k+1\]\[r\]$ * 按什么顺序进行DP？ 区间长度从小到大的顺序。 （或者：记忆化搜索） * 时间复杂度：$O(n^3)$ #### 矩阵链乘法 * 将一个$p \\times q$的矩阵乘一个$q \\times r$的矩阵，得到一个$p \\times r$的矩阵，运算花费是$p \\times q \\times r$。 * 现在输入$p\_1,p\_2,p\_3,...,p\_n$。将$p\_1 \\times p\_2,p\_2 \\times p\_3,...,p_{n-1} \\times p_n$的矩阵乘起来，最小的总运算花费是多少？ #### 例题n（记不清了）  \- 设计状态： $f\[l\]\[r\]$表示$a\[l,r\]$字串的答案。 - 转移：$f\[l\]\[k\]+f\[k+1\]\[r\]$ 当a\[l\]==a\[r\]时，未完。。。 #### Floyd也是dp * n个点的无向图，有向点和边权。每一对s，t，计算从s到t的路径，使得最小化：路径上的总边权+路径最大点权 * $(n\\leq300)$ ### 状态压缩DP #### 经典问题 * 求n个点的无向图的色数。（可以把顶点染成k种颜色之一，使得每条边两端不同色。最小的k是多少） * $n\\leq16$ * 设计状态，用f\[s\]表示结点子集S的色数。枚举子集进行转移。 * $f\[S\]=min(f\[S\],1+f\[S-T\])$，T是S的子集$((T\\&S)==t)$，T中的点两两不相邻。 Last modification：March 14, 2020 © Allow specification reprint Like 1 如果觉得我的文章对你有用，请随意赞赏