状态型

状态机约束，作为一层状态

一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值。一般 j 都很小。代表题目是「买卖股票」系列。

• 乘积最大子数组

  最大/最小值

• 买卖股票的最佳时机

  是否持有股票

• 粉刷房子

  粉刷哪种颜色

注：某些题目做法不止一种，除了状态机 DP 以外，也有前后缀分解的做法。