0%

动规递推式浅解

发表于 更新于 分类于
对一些常见的dp递推进行了整理
  • 第一类斯特林数

f[n][k]=f[n−1][k]∗(n−1)+f[n−1][k−1]

1
n个不同元素k个不同环，环不空
  • 第二类斯特林数

f[n][k]=f[n-1][k]*k+f[n-1][k-1]

1
n个不同元素k个相同集，集不空
  • 卡特兰数

f[n]=f[n-1]*(4n-2)/(n+1)

f[n]=$C^{2n}_{n}/(n+1)$

1
2
3
4
5
n对括号，正确匹配方案数
n个节点，二叉树构造方案数
n边形，凸多边形划分为三角形方案数
n个元素，出栈序列种数
2n的(-1,1)序列，使任意前缀非负的方案数
  • 01背包

f[i][j]=sum/max/min(f[i-1][j],f[i-1][j-w[k]]+v[k])

  • 多重背包

f[i][j]=sum/max/min(f[i-2^p][j],f[i-2^p][j-w[k][p]]+v[k][p])

1
把物品二进制拆分成很多个物品，倍增思想
  • 区间动规

f[i][j]=sum/max/min(f[i][k]+f[k+1][j]+g(i,j))

1
2
3
k为断点,g(i,j)为[i,j]区间相关代价函数
枚举断点进行递推
常见于合并区间，回文对应，左右子树配对等
  • 树形动规

f[i][j]=sum/max/min($\sum_{k∈son_i}f[k][g(j)]$)

1
2
3
g(j)是关于状态j的函数，通常是0/1
表示选不选，染什么色，左儿子还是右儿子等等
常见于树形分组背包，树的直径，树上01问题等
  • 状压动规

f[i][j][k]=sum/max/min($\sum_{p∈S(j)}$f[i-1][p][k-1])

1
2
3
4
i,j,k:行数,状态,数量
S(j)为与j状态能够相容的状态集合
可以转化为类01背包问题
往往用于合法放置方案数问题
  • 单调队列优化式

f[i]=min/max$\sum_{j=i-m+1}^{i}$a[j]

1
2
3
序列中长为m的滑动窗口最值问题
最大连续和，定长连续子区间最值
队列滚维
  • 斜率优化式

f[i]=min{f[j]+(g(i)-g(j))$^2$}

1
2
3
下标为横，值为纵，构造斜率。
单调队列维护下凸壳。
如果凸壳需要动态化，使用平衡树插入/删除维护下凸即可
  • 目前整理内容均比较粗略，后续会进行补充。