零散点小总结(25.10.28)

今天练习了Dp,主要把Dp重新看待了一下,有以下几点

  1. Dp其实本质是一种表,用于储存子问题的答案
  2. Dp中其实还有枚举,只是由于子问题被存入表中了,所以减少了时间复杂度
  3. 一个搜索其实就是Dp的暴力解,有很多的子问题,但是由于重复会使时间很大
  4. 所以变相的看一下,如果使搜索的每个状态下都做到最优,就可以方便后面的求解,所以Dp的最优子结构相当于松弛,使每个最小
  5. 所以在写Dp可以从搜索入手,先把搜索写出来,之后看搜索用了哪些状态和如何转移决策,用于启发自己的Dp状态设计
  6. 其实有很多时候记忆化搜索 $≈$ Dp
  7. 然后再提一下记忆化搜索,是记录每种状态,然后去进行搜索,所以要注意每种选择/约束的状态,可以用于设置记忆数组