Ricky.L的随笔
0%

LeetCode.188.买卖股票的最佳时机 IV（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.188.买卖股票的最佳时机 IV（困难）

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题解

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

看最终结果受哪些因素影响，穷举不同因素的所有状态值，就可以推导出最终结果。

最终收益受哪些维度的状态变化影响？

  • 在第几天买入或卖出肯定是会影响最终收益，可能某一天突然暴涨。
  • 交易次数越多，可能赚取的收益越大。
  • 在第i天可以选择的操作有三种：买入、卖出、什么也不做。
    什么也不做包含了两种状态：买入过后什么也不做、卖出过后什么也不做。归纳合并一下，这些操作会产生的结果状态是：第i天持有或不持有股票。股票持有状态也会影响最终收益。

所以从结果上看，一共有三种纬度的状态变化：

  • 第几天做出选择
  • 已经交易了多少次
  • 当前是否持有股票

买入的时候算一次交易，还是卖出的时候算一次交易？

其实都可以，不影响最终结果，只是状态转移过程会有所变化。
这里定义买入的时候算一次交易。

状态转移方程

dp[i][j][k]表示，前i天，交易了j次，在第i天持有或不持有股票，所获得最大的收益。其中k == 0表示不持有，k == 1表示持有。

  • dp[i][j][0]怎么得来？
    • 第i - 1天没有持有股票，第i天什么也不操作。
      • dp[i][j][0] = dp[i - 1][j][0]
    • 第i - 1天持有股票，第i天卖出。
      • dp[i][j][0] = dp[i - 1][j][] + prices[i]
  • dp[i][j][1]怎么得来？
    • 第i - 1天持有股票，第i天什么也不操作。
      • dp[i][j][1] = dp[i - 1][j][1]
    • 第i - 1天没有持有股票，第i天买入。
      • dp[i][j][1] = dp[i - 1][j - 1][0] - prices[i]

边界处理

  • 第0天
    • 持有股票的话，不多少次交易，只能直接买入一次。
    • 不持有股票的话，收益就是0。
  • 第i天之前都没有交易即j == 0），第i天要交易操作就买入。

空间优化

如果给定的最多交易次数k非常大，状态数组开辟空间也会非常大，的。

交易上限是多少？

一次交易要买入和卖出，总共n天，交易次数不应该超过n / 2。

交易次数超过n / 2要怎么办？

这就等于不限交易次数，与LeetCode.122.买卖股票的最佳时机 II（简单）解法相同，可以复用这种情况下最优化空间的解答。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    fun maxProfit(k: Int, prices: IntArray): Int {
        if (prices.isEmpty() || k == 0) return 0
        val n = prices.size
        if (k >= n / 2) {
            return maxProfitNonLimitCount(prices)
        }
        // 三种状态：第几天买入或卖出、已经交易了多少次、当前是否持有股票
        // dp[i][j][0或1]表示，前i天，交易了j次，在第i天持有或不持有股票，所获得最大的收益
        // 这里定义买入的时候算一次交易
        val dp = Array(n) { Array(k) { IntArray(2) { 0 } } }
        for (i in 0 until n) {
            for (j in 0 until k) {
                if (i == 0) {
                    // 第0天持有股票的话，最多k次交易，只能直接买入
                    dp[i][j][1] = -prices[i]
                } else {
                    // 第i天，交易了j次，持有股票
                    // 可能是前i-1天就交易了j次并持有股票，也可能前i-1天交易了j-1次在今天买入了
                    // 如果之前没有交易，今天就直接买入就好了
                    if (j == 0) {
                        dp[i][j][1] = maxOf(dp[i - 1][j][1], -prices[i])
                    } else {
                        dp[i][j][1] = maxOf(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
                    }
                    dp[i][j][0] = maxOf(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                }
            }
        }
        return dp[n - 1][k - 1][0]
    }

    private fun maxProfitNonLimitCount(prices: IntArray): Int {
        val n = prices.size
        if (n == 0) return 0
        var holdProfit = -prices[0]
        var noholdProfit = 0
        for (i in 1 until n) {
            val newHoldProfit = maxOf(holdProfit, noholdProfit - prices[i])
            val newNoholdProfit = maxOf(noholdProfit, holdProfit + prices[i])
            holdProfit = newHoldProfit
            noholdProfit = newNoholdProfit
        }
        return noholdProfit
    }
}

复杂度

  • 时间复杂度O(n * k)。
  • k >= n / 2时，空间复杂度O(1)；k < n / 2时，空间复杂度O(n * k)。