Ricky.L的随笔
0%

LeetCode.309.最佳买卖股票时机含冷冻期（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.309.最佳买卖股票时机含冷冻期（中等）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

题解

最优化问题考虑用动态规划。

步骤拆分

第i天的基本操作有：买入、卖出、什么都不做。
买入有冷冻期限制，第i天可能无法买入，也就是只能什么都不做了，所有的操作还是这三种，不影响确定最终状态。
经过选择操作后可得第i天的最终状态只有：持有股票或不持有股票。
买入冷冻期的限制在状态转移方程中做状态转移时体现出来就行。

状态转移方程

设dp[i][k]为前i天最大利润，k = 0表示第i天不持有股票，k = 1表示第i天持有股票。

dp[i][0]有两种可能的操作得到：

  1. 第i天什么都不做，利润和前i - 1天一样
  2. 之前持有股票，第i天卖出

可得dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])

dp[i][1]有两种可能的操作得到：

  1. 第i天什么都不做，利润和前i - 1天一样
  2. 之前不持有股票，第i天买入；买入有冷冻期限制，如果是第i - 1天卖出的，第i天就不能买入了。

可得dp[i][1] = max(dp[i - 1], dp[i - 2][0] - prices[i])

空间优化

dp[i][k]只与前面两个状态有关，用变量记录前面的状态，不需要数组记录所有状态。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    fun maxProfit(prices: IntArray): Int {
        val n = prices.size
        if (n <= 1) return 0

        // i == 0
        var preNoholdProfit = 0
        var preHoldProfit = -prices[0]

        // i == 1
        var curNoholdProfit = maxOf(preNoholdProfit, preHoldProfit + prices[1])
        var curHoldProfit = maxOf(preHoldProfit, preNoholdProfit - prices[1])

        for (i in 2 until n) {
            val newNoholdProfit = maxOf(curNoholdProfit, curHoldProfit + prices[i])
            // 买入有冷冻期，只能从前天没有持有股票的状态转移而来
            val newHoldProfit = maxOf(curHoldProfit, preNoholdProfit - prices[i])

            preNoholdProfit = curNoholdProfit
            preHoldProfit = curHoldProfit

            curNoholdProfit = newNoholdProfit
            curHoldProfit = newHoldProfit
        }

        return curNoholdProfit
    }
}