树形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]采集资源（背包）