LeetCode 309 最佳买卖股票时机含冷冻期

本题是一到很好地集合了状态机和动态规划的例题，能够很好的体会状态机思想对复杂动态规划问题的简化。

题目描述

原题链接如下： LeetCode 309 最佳买卖股票时机含冷冻期

题目大意

问题中只有一只股票，而每次进行股票的卖出操作都会引入一天的冷冻期，求出如此条件下买卖股票的最大利润。

输入与输出

示例输入为：

1

[1,2,3,0,2]

要获得最大利润，就应该对应进行如下操作：

1. 买入
2. 卖出
3. 处于冷冻期，无法操作
4. 买入
5. 卖出

对应输出为：

1

3

解题思路

一般的股票问题可以使用动态规划思想简单解决，但是本题因为引入了冷冻期问题导致子问题非常复杂，需要分情况讨论。同时，我们要注意动态规划问题的子问题不是静态的，需要在遍历时进行状态转移操作，尤其是子问题的各个情况可能交叉转移到下一个子问题的不同情况，这样问题会更加复杂。 为了处理此类问题，我们需要借助有限状态机思想，简化动态规划的状态转移操作。

确定状态机模型

每天的股票交易操作进行完毕之后，可能有如下的不同状态：

• 持有股票
• 未持有股票
  • 处于冷冻期
  • 未处于冷冻期

所有我们的状态机模型中共有 3 个状态，它们的关系如下所示：

需要注意的是，冷冻期只有一天，所以处于在 frozen 状态时再进行等待操作就只能进入 empty 状态。

确定状态转移方程

首先，先确定子问题的状态表示方法，对应上文的有限状态机模型本题中每天的利润可能有 3 种情况，分别是：

• $full(i)$
• $frozen(i)$
• $empty(i)$

然后，再把状态转移方程对应到状态机模型中的操作部分，要使用 3 种状态方程，分别是：

$$ \begin{aligned} full(i) &= \max {(full(i - 1), empty(i - 1) - prices[i])}\\ frozen(i) &= full(i - 1) + prices[i]\\ empty(i) &= \max {(frozen(i - 1), empty(i - 1))} \end{aligned} $$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maxProfit(prices: IntArray): Int {
        if (prices.isEmpty()) return 0
        val n = prices.size
        var full = -prices[0]
        var frozen = 0
        var empty = 0
        for (i in 1 until n) {
            val nextFull = maxOf(full, empty - prices[i])
            val nextFrozen = full + prices[i]
            val nextEmpty = maxOf(frozen, empty)
            full = nextFull
            frozen = nextFrozen
            empty = nextEmpty
        }
        return maxOf(frozen, empty)
    }
}

注意：

• 状态转移方程虽然有 3 种，但是都之和前一项有关，所以无需使用 3 个数组存储数据，只是用 3 个整数变量即可
• 如果不使用数组，则需要注意要在所有新状态的结果都算完之后才能统一更新状态