几种不同类型的dp问题小结

作者： 作者的头像   zhengyh ,  2020-04-04 16:22:40 ,  所有人可见 ,  阅读 1001

3


dp的递推算法

  1. 背包问题
  2. 线性dp
  3. 区间dp (状态表示的维度都是表示一个区间)
  4. 计数dp (维护特性为数量的dp)
  5. 数位dp (重点在于分类讨论)
  6. 状压dp -> 状态压缩专题整理
    (状态压缩问题的状态的个数一般不会很多, 因为我们要把状态压缩到一个整数里面, 所以n == 20已经是极限了,一般n比较小的时候我们考虑用状态压缩dp)

dp的递归算法

  1. 树形dp
  2. 记忆化搜索

会持续更新..

0 评论