状态机

以 309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode） 为例

第一步：确定状态

状态分为3种：

1. 持有股票

2. 不持有股票，之后一天处于冷冻期

3. 不持有股票

我们以 f[i] 来表示 i 天之后的最大利益，则以上3种状态即为：

1. $$f[i] [0]$$

2. $$f[i] [1]$$

3. $$f[i][2]$$

第二步：状态转移

我们有如下分析：第i天时，我们可以进行 买入 或者 卖出 或者 不操作 的操作，或者处于 冷冻期 时，我们不能进行 买入 的操作，因此对于以上3种状态有如下分析：

• 对于 f[i] [0] 时，第 i 天处于 持有股票 的状态，这支股票可能是第 i - 1 天买入的股票，因此对应的第 i - 1 天的状态为f[i - 1] [0]；同样存在可能，第 i 天买入，则第 i 天不处于冷冻期，所以存在可能f[i - 1] [2]，状态转移方程即为：

  $$f[i][0]=max(f[i -1][0], f[i-1][2]-prices[i])$$

• 对于f[i] [1] 时，第 i 天处于 不持有股票且处于冷冻期 的状态，因此第 i - 1 天必然卖出了股票，因此对应的第 i - 1 天的状态为f[i - 1] [0]，状态方程即为：

  $$f[i][1] = f[i-1][0]+prices[i]$$

• 对于f[i] [2] 时，第 i 天处于 不持有股票且不处于冷冻期 的状态，说明第 i - 1 天可能处于冷冻期，因此对应的状态为 f[i - 1] [1]；同样也有可能第 i - 1 天没有进行任何操作，因此对应的状态为 f[i - 1] [2]，状态转移方程即为：

  $$f[i][2] = max(f[i - 1][1], f[i - 1][2])$$

这样我们就得到了所有的状态转移方程。如果一共有 n 天，最终的答案即为：

$$f_m = max(f[n - 1][0], f[n - 1][1], f[n - 1][2]) = max(f[n - 1][1], f[n - 1][2])$$

第三步：代码实现

我们可以将第 0 天作为动规边界条件：

$$\left\{ \begin{matrix} f[0][0] = -prices[0] \\ f[0][1] = 0 \\ f[0][2] = 0 \end{matrix} \right.$$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f0, f1, f2 = -prices[0], 0, 0
        for i in range(1, n):
            fn0 = max(f0, f2 - prices[i])
            fn1 = f0 + prices[i]
            fn2 = max(f1, f2)
            f0, f1, f2 = fn0, fn1, fn2
        return max(f1, f2)

基本上和Leetcode上的官方题解差不多，因为我是边看题解边理解边写的