马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
1、背包DP
- 01 01 01背包：罗列物品然后罗列体积，体积从大到小罗列更新 f [ j ] = m a x ( f [ j ] , f [ j − w ] + v ) f[j]=max(f[j],f[j-w]+v) f[j]=max(f[j],f[j−w]+v).
- 完全背包：罗列物品然后罗列体积，体积从小到大罗列更新 f [ j ] = m a x ( f [ j ] , f [ j − w ] + v ) f[j]=max(f[j],f[j-w]+v) f[j]=max(f[j],f[j−w]+v).
- 多重背包(物品有 k k k个)：罗列物品后，二进制方式罗列物品件数。体积从大到小罗列，更新： f [ j ] = m a x ( f [ j ] , f [ j − k ∗ w ] + k ∗ v ) f[j]=max(f[j],f[j-k*w]+k*v) f[j]=max(f[j],f[j−k∗w]+k∗v).末了判断剩余 s s s是否大于0，如果大于0再做一遍 01 01 01背包。
- 混淆背包(前三种混淆体)：有限个物品则用多重背包方式优化做，无限物品则完全背包做。
- 分组背包(每个组只能选1个)：一维方法：先罗列体积后罗列物品，且体积罗列从大到小同时需要罗列到0。二维方法先罗列物品再罗列体积，体积也从大罗列到小需要罗列到0.
- 依赖背包(树形背包)：状态界说 f [ u ] [ i ] f f以 u u u为根节点的子树中 i i i体积最多可以得到的价值，需要通过回溯再继续更新 f [ u ] [ j ] = m a x ( f [ u ] [ j ] , f [ u ] [ j − k ] + f [ v ] [ k ] ) f[j]=max(f[j],f[j-k]+f[v][k]) f[j]=max(f[j],f[j−k]+f[v][k]).每次递归需要预处理出 f [ u ] [ i ] f f的值。更新先罗列总体积 j j j从大到小罗列 [ V , w e i [ u ] + w e i [ v ] ] [V,wei+wei[v]] [V,wei+wei[v]].然后罗列分配到子节点的体积 [ w e i [ v ] , u − w e i [ u ] ] [wei[v],u-wei] [wei[v],u−wei].
2、线性DP
- 数字三角形模子
- 朴素版：只能从上走下来和从左边走过来 f [ i ] [ j ] = m a x ( f [ i ] [ j − 1 ] , f [ i − 1 ] [ j ] ) + w [ i ] [ j ] f[j]=max(f[j-1],f[i-1][j])+w[j] f[j]=max(f[j−1],f[i−1][j])+w[j].
- 走的方块数量限制：曼哈顿距离 ( 1 , 1 ) − > ( n , n ) (1,1)->(n,n) (1,1)−>(n,n)为 2 n − 2 2n-2 2n−2.所以思量是不是走的最短路
- 走两条路：状态界说 f [ k ] [ i ] [ j ] f[k][j] f[k][j]表现路径的长度为 k k k，第一条路径到达 x 1 = i x_1=i x1=i，第二条路径到达 x 2 = j x_2=j x2=j的方案数。因此状态转移： f k , i , j = m a x { f k − 1 , i , j , f k − 1 , i − 1 , j , f k − 1 , i , j − 1 , f k − 1 , i − 1 , j − 1 + w } f_{k,i,j}=max\{ f_{k-1,i,j},f_{k-1,i-1,j},f_{k-1,i,j-1},f_{k-1,i-1,j-1}+w \} fk,i,j=max{fk−1,i,j,fk−1,i−1,j,fk−1,i,j−1,fk−1,i−1,j−1+w}
- 两条路径不能交叉，实际证明按上面的方式做就可以，上面的最优环境是可以酿成不经过重复门路。
- 最长上升子序列模子
- 最长公共子序列： O ( n 2 ) O(n^2) O(n2)，方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[j]=max(f[i-1][j],f[j-1]) f[j]=max(f[i−1][j],f[j−1])，如果 a [ i ] = = b [ i ] , f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − 1 ] + 1 ) a==b,f[j]=max(f[j],f[i-1][j-1]+1) a==b,f[j]=max(f[j],f[i−1][j−1]+1)
- 最长公共子串： O ( n 2 ) O(n^2) O(n2)，方程： f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − 1 ] ) f[j]=max(f[j],f[i-1][j-1]) f[j]=max(f[j],f[i−1][j−1]).
- 最长上升子序列：
- 方式1： O ( n 2 ) O(n^2) O(n2)，状态 f [ i ] f f表现前 i i i个数的最长上升子序列长度，更新：从 j ∈ [ 1 , i ) j \in[1,i) j∈[1,i)找到每一个 a [ j ] < = a [ i ] a[j]<=a a[j]<=a更新 f [ i ] = m a x ( f [ i ] , f [ j ] + 1 ) f=max(f,f[j]+1) f=max(f,f[j]+1).
- 方式2： O ( n l o g n ) O(nlogn) O(nlogn)，用一个列表存储一个上升子序列，当 a [ i ] > s [ − 1 ] a>s[-1] a>s[−1]时将 a [ i ] a a加入到 s s s中，小于时，二分查找 s s s列表找到第一个大于等于 a [ i ] a a的值用 a [ i ] a a替换掉。
3、状压DP
- TSP题目：界说状态 f [ i ] [ j ] f[j] f[j]表现当前已近到达的状态为 i i i，末了到达的城市是 j j j，基本的状态转移方程为： f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ′ ] [ k ] + d [ j ] [ k ] ) f[j] = min(f[j],f[i'][k]+d[j][k]) f[j]=min(f[j],f[i′][k]+d[j][k])，基于当前的状态 i i i罗列前一个状态 i ′ i' i′，每次尝试更新从 i ′ i' i′到 i i i，其中 i ′ i' i′状态末了到达的是 k k k节点，然后更新是从 k k k走到 j j j。时间复杂度 O ( n 2 ∗ 2 n ) O(n^2*2^n) O(n2∗2n)这里的 n n n的大小一般小于等于 18 18 18.
- 状压一般就是罗列两个状态，当前状态和可以或许影响当前状态的前一状态，通过前一状态转移到当前状态。状态之间的转移一般比较容易。
4、数位DP
- 数位 D P DP DP基本可以套板子，主要题目就是思量前导0是否影响答案，也就是思量 023 023 023和 23 23 23的区别有没有。下面是通用的板子。其他参数只有 t o t a l total total是需要被思量的。 i s _ l i m i t is\_limit is_limit表现的是到达了上线的数字。 i s _ n u m is\_num is_num是表现是否是非0的数字
- from functools import lru_cache
- @lru_cache(maxsize=None)
- l,r = map(int,input().split())
- def f(s,i,total,is_limit,is_num,res=0):
- if i==len(s):
- return total #是否符合条件
- # 如果023和23有区别则需要处理前导0
- if not is_num:res += f(s,i+1,0,False,False)
- up = int(s[i]) if is_limit else 9
- for d in range(1-int(is_num),up+1):
- res += f(s,i+1,total+某个值,is_limit and d==up,True)
- return res
- print(f(str(r),0,0,True,False)-f(str(l-1),0,0,True,False))
- # 如果计算f(r)和f(l-1)时会有关联可以计算一个后清空cache
- f.cache_clear()
5、树型DP
- 求树的最大权值：类似于求最大子段和，只不过在树上，每次递归的时间先初始化 f [ u ] = a [ u ] f=a f=a，然后递归 u u u节点的每一个子节点，回溯的时间举行更新 i f f [ v ] > 0 : f [ u ] + = f [ v ] if \ f[v]>0:f+=f[v] if f[v]>0:f+=f[v]
- 求树的直径：第一次从根节点 d f s dfs dfs递归到一个深度最大的节点 s s s，然后以 s s s以根节点递归都得一个最大深度的节点 p p p，那么节点 s s s到 p p p就是树的直径。递归每个节点的儿子节点时碰到父节点跳过。
- 树型 D P DP DP的基本思路是递归的开始举行预处理，然后罗列根节点的每个儿子节点，对儿子节点举行递归，回溯的时间再举行更新。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
