DP的优化

[DP的三要素]

状态 决策 转移

[DP的时间复杂度]

DP时间复杂度=状态总数 * 每个状态转移的状态数 * 每次状态转移的时间复杂度

[DP的优化方向]

减少状态总数

1.改进状态表示（如三维变二维）

2.更换更好的规划办法（如思路重构）

减少决策时间复杂度

1.四边形不等式和决策单调性优化

2.决策量优化（剪枝）

3.合理组织状态（抽象）

4.对状态转移加以限制

5.空间时间互换（通常是空间换时间）

减少每次状态转移的时间复杂度

1.矩阵加速递推

CHAPTER 1 矩阵加速递推

实质：减少每次状态转移的时间复杂度，即优化“转移”