动态规划tips

树形dp 一般的转移方式：dfs

• 状态的设置一般为：f[当前节点][当前节点（或以节点为根的子树）的状态（特殊点有多少个、该节点染什么色等）] 表示的一般是 以当前节点为根的子树对答案的贡献（或最值等）。
• 给出的是无根树，一般有以下情况：
  a.枚举根的时间复杂度能过的
  b.随便一个点为根都行的
  c.先随便一个点来dp，然后再进行换根操作的（二次扫描换根法）（例子：POJ3585）
• 与背包问题的结合（例题：二叉苹果树）

期望dp

• 倒序（递归）进行dp

区间dp

• 枚举区间长度，再枚举左端点

背包问题

• 一维1到n
• 01背包：二维m到v_i
• 完全背包：二维v_i到m
• 多重背包：二进制拆分为01背包

区间dp

• 状态设置的一般形式：f[i][j]表示区间[i,j]所处理出的答案（按照需要可以多加维度）
• dp过程：
  • 枚举长度l与区间左端点i，表示区间[i,i+l-1]的答案。
    区间dp通常是由小区间的答案推到大区间的答案，所以要先枚举长度
  • 按照题目需要进行循环的添加（如[CQOI2007]涂色就需要枚举一个断点）
• 思路
  • 若从数据看出题目的时间复杂度为O(n^3)，则需要考虑枚举断点
  • 若能从数据看出题目的时间复杂度为O(n^2)，则一般要考虑区间[i,j-1]加上元素j与区间[i+1,j]加上元素i对区间[i,j]的影响，进而推出dp式

dp的优化

• 三方面：
  a.状态的设置（如三维转二维）
  b.转移过程的优化
  c.转移状态的减少
• 有多个操作或维度，进行简化

千奇百怪的dp

• 二次dp:[GDOI2014]采集资源（背包）