我的一些DP理解_yby

主题思想

• • 确定是否可以DP解决
    • 首先，自己不太明确类型的题（一般来说，计算几何，数据结构，数学，字符串，图论的一部分题能很容易一眼看出题目类型），很有可能是DP、网络流、或者乱搞。
    • 用DP来思考问题的话，首先就是能否设计出无后效性的状态（简单来说就说状态是一个DAG（有向无环图）图上的点，转移就是边），然后看能否满足复杂度。。。
    • 其实就是一个不断试错的过程。
  • 一般解决套路
    • 子问题的确立（有时候可以没有？我理解的不是很深刻）
    • 状态的确立（压缩状态数，看状态数是否足够）
    • 状态转移怎么转移？
    • 复杂度的计算，一般来说 复杂度=状态数*转移复杂度
    • 复杂度不够的话，考虑能不能优化DP方程的转移。还是不行的话，重新确立状态。
    • 复杂度可以，考虑边界条件的处理
    • 考虑DP写法
    • 实现
• 两种常见的DP写法
  • 记忆化搜索（强烈建议熟练这种写法，非常好用）
  • 常规的递推（一般来说，要优化的话，只能对递推的形式进行优化）
  • 所以上述两种一般得都会
• DP几种套路题
  • 线性DP
    • 常规的LIS，LCS等
    • 一般理解具体的DP思想就好吧。
  • 背包DP
    • 几种典型背包，可见：背包九讲
  • 区间DP
    • 很套路的题，一般都是一眼题，建议使用记忆化搜索
    • 做过几个典型就全会了（可能只用一个？）
    • 记忆化搜很好写
  • 概率DP
    • 一般来说概率DP的套路也很固定。
    • 一般来说概率相关问题的解法，很多情况下和期望相关
    • 有的时候，会转化成解方程的形式，然后高斯消元
    • 这种类型的题也是做几个就全会了
  • 树形DP
    • 树形DP一般是在树上搞事情
      • 插一嘴，树相关的题一般树形DP或者数据结构，别的题基本没有
    • 树形DP也有几种比较固定的状态的设计
    • 树形DP难的挺多的
  • 数位DP
    • 很套路的题，建议使用记忆化搜索
    • 解决的问题都是按数位处理（做过几题之后看到就知道是不是这个类型，一般来说看数据规模）
  • 状压DP
    • 很多比较难的题。。。或者说最难的题一般都与此相关
    • 主要的思想就是对状态按位压缩，一般是二进制，插头是三进制？
    • 按位压缩的状态压缩很关键
  • 连通性DP
    • 一般来说代码量比较大，也有套路，但是我其实不是很会orz。。
    • 插头DP
      • 其中一种类型，代码量挺大，麻烦。。。我也不会
  • 博弈及其相关
    • 很多情况下，博弈其实也是状态转移，所以和DP很像的
  • 字符串及其相关
    • 一般来说，涉及到序列的题，都是DP。
    • 字符串的题都是那些字符串做法（后缀数组啥的）
    • 意思就是要不要求连续的
  • 其他比较难的套路
    • 几种计数DP
      • 好多好多啊，一般经常会和数学结合在一起
      • 组合数学相关题比较多。。
      • 感觉能出的巨难。。。
    • DP套DP
      • 难，但是有套路
    • 斯坦纳树
      • spfa
    • 高维的题
      • 我不会。。。
• DP优化套路
  • 矩阵快速幂
    • 一般对于一种线性递归方程，然后某一维很大的情况
    • 这种情况下，我们可以推出一个转移矩阵，然后就可以矩阵快速幂了
  • 斜率优化
    • 一种很常见的优化姿势
    • 运用到数形结合的思想
    • 做几道就有感觉了？
  • 平行四边形优化
    • 对二维状态的优化，题目比较少。。。
    • 我也没做过几道
  • 数据结构优化
    • 常见的有线段树优化等
    • 其他的见得不是很多
  • 状态不连续
    • 使用指针之类的？
    • map Hash
  • 计数的套路
    • 容斥
    • 数学相关知识
  • 黑科技
    • bitset
      • 不要使用循环，不然效率很低下
    • 各种剪枝乱搞