状态机 DP
笔者其实更愿意称之为“分类DP”。
状态机本身概念与算法无关，选择性理解。
解释：包含多个待选状态，不同的状态之间有相互转化的方法，我们可以借助这些转化的手段，达成状态之间的相互转移。
例 $1$：
给定一支股票 $n$ 天的价格 $a_i$，最多持有一只股票，买入卖出共视作一次交易，最多进行 $k$ 次交易，求最大收益。
买入/卖出是通过卖出/买入的状态转移来的，而不是通过更小规模的相同结构转移过来，称这样的 DP 过程为状态机 DP。
状态：
设 dp$[i][j][0/1]$ 表示到第 $i$ 天，共进行 $j$ 次交易，且第 $i$ 天为买入/卖出的最大收益。
转移：
$(i,j,0)\leftarrow(i-1,j-1,1),(i-1,j,0)$
$(i,j,1)\leftarrow(i-1,j,0),(i-1,j,1)$
DP 式子：
For(i,1,n) For(j,1,k) dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]-a[i]),dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][0]+a[i])
空间上显然可以滚动数组优化。
时间复杂度：$O(nk)$。
空间复杂度：$O(k)$。
例 2：
给定一支股票 $n$ 天的价格 $a_i$，最多持有一只股票，买入卖出共视作一次交易，卖出股票后第二天不能买入，求最大收益。
状态：
设 dp$[i][j][0/1/2]$ 表示到第 $i$ 天，共进行 $j$ 次交易，且第 $i$ 天为买入/卖出/不操作的最大收益。
转移：
$(i,0)\leftarrow(i-1,0),(i-1,2)$
$(i,1)\leftarrow(i-1,0)$
$(i,2)\leftarrow(i-1,2),(i-1,1),(i-1,0)$
DP 式子：
For(i,1,n) dp[i][0]=max(dp[i-1][0],dp[i-1][2]-a[i]),dp[i][1]=dp[i-1][0]+a[i],dp[i][2]=max(dp[i-1][2],max(dp[i-1][0],dp[i-1][1]))
同样地容易得出可以滚动数组优化空间。
时间复杂度：$O(n)$。
空间复杂度：$O(1)$。