股票买卖问题

股票买卖问题也是一种很典型的动态规划题型。通过对力扣上一系列此类问题的分析来记录这一类问题的解题思路与技巧。

最佳买卖股票时机 1（只能买卖 1 次）

leetcode 121

1
2
3
4
5
6
7
8
9
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

动态规划解法

问题分析

本题是股票题型吃的基础问题，规定只能买卖各一次，所以在每一个交易日，股民只有两种状态：

  • 持有（可能是当天购买，也可能是在前面的交易日就已经购买了）
  • 不持有

$dp$ 数组定义

因为股票的价格是变动的，而买入时所花费的额度是固定的，最终能获得的收益只有在股票卖出时才能确定。所以我们假设初始状态下手中的现金数是 $0$，那么在第 $i$ 天买入手中剩余的现金就是 $0 - prices[i]$

$dp[i][0]$ 表示第 $i$ 天持有，剩余的现金数。

$dp[i][1]$ 表示第 $i$ 天不持有，手中剩余的现金数。

递推公式

第 $i$ 天持有有两种情况：

  • 第 $i$ 天买入，那么第 $i - 1$ 天必然为不持有，所以买入后剩余现金为 $0 -prices[i]$
  • 第 $i-1$ 天时就已经处于持有状态，那么必然与第 $i-1$ 天保持一致，为 $dp[i - 1][0]$。

两者取最大值：

第 $i$ 天不持有同样有两种情况：

  • 第 $i$ 天卖出，那么第 $i - 1$ 天必然持有，所以卖出后剩余现金就是第$i-1$ 天持有剩余的现金加上第 $i$ 天的股票价格， $dp[i-1][0] + prices[i]$
  • 第 $i-1$ 天时就已经处于不持有状态，那么必然与第 $i-1$ 天保持一致，为 $dp[i - 1][1]$。

两者取最大值：

dp数组初始化

边界条件就是第一天，后面每个交易日的推导都是从第一天开始，第一天在两种状态下剩余剩余的现金为：

  • 买入：$-prices[0]$
  • 不买入：$0$

确定遍历顺序

由上分析第 $i$ 天的状态依赖于第 $i-1$ 天的状态，所以从前向后遍历。

举例推导

以题目示例为例，直接展示一下推导的最总终结果：

获取结果

通过递推公式的状态转移推导，最大的收益必然是经过了所有交易日后，在最后一个交易日处于不持有状态时的剩余现金。

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    //定义起始状态现金是0
    //dp[i][0] 第i天持有，手中剩余的现金
    //dp[i][1] 第i天不持有，手中剩余的现金
    dp[0] = []int{-prices[0], 0}
    for i := 1; i < len(prices); i++ {
        dp[i] = make([]int, 2)
        //第i天持有，有两种情况
        //1 第i天买入
        //2 第i-1天就已经持有
        dp[i][0] = max(-prices[i], dp[i - 1][0])

        //第i天不持有，有两种情况
        //1 第i天卖出，剩余现金就是卖出的价格加上第i-1天持有时剩余的现金
        //2 第i-1天就已卖出，剩余现金就等于第i-1天不持有剩余的现金
        dp[i][1] = max(prices[i] + dp[i - 1][0], dp[i - 1][1])
    }
    return dp[len(prices) - 1][1]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

根据 $dp$ 数组的定义与推导分析，每一天的状态只依赖于前一天的状态，在计算完第 $i$ 天的状态后，第 $i - 1$ 天的状态已经不再需要了，所以我们可以只定义一个长度为 $2$ 的一维 $dp$ 数组，$dp[0]$ 表示第 $i$ 天持有，$dp[1]$ 表示第 $i$ 天不持有，每一次遍历就将数组的两个状态计算并覆盖，最终得到的就是表示最后一个交易日的状态的数组，而 $dp[1]$ 就是答案。

这样就能够把算法的空间复杂度优化到 $O(1)$。

贪心解法

问题分析

本题限制只能买卖一次股票，所以利用贪心思想：

对于所有的交易日，只要在左侧最低的价格买入，在右侧最高的价格卖出，这样就得到了最大的收益。

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int) int {
  	//寻找最左侧最低的价格，就必须要把low初始化为极大值，否则就一直是0了
    low := math.MaxInt64
    var res int
    //遍历每一个交易日
    for i := 0; i < len(prices); i++ {
      	//遍历过的交易日的股票最小价值
        low = min(low, prices[i])
      	//交易日股票价值减去历史最小值取最大值
        res = max(res, prices[i] - low)
    }
    return res
}

时间复杂度 $O(n)$

空间复杂度 $O(1)$

买卖股票的最佳时机 2（可以买卖多次）

leetcode 122

1
2
3
4
5
6
7
8
9
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

问题分析

本题不再是只能进行一次买卖，而是可以在交易日内完成任意次交易，但是不能同时参与多笔交易，也就是买入操作必须在不持有的状态下才能进行。

与上一题唯一的区别是在推导 $dp[i][0]$ 的时候，上一题中，因为只能进行一次交易，所以在计算买入状态时，它就必然是第一次买入，也就是 $-prices[i]$。

而本题中，可以进行任意次交易，当计算某个交易日的持有状态 $dp[i][0]$ 时，可能在此之前已经完成了若干笔交易，那么手中剩余的现金可能就不是 $0$ 了，所以当日买入后剩余的现金就是前一个交易日卖出后剩余的现金减去当日股票价格， $dp[i - 1][1] - prices[i]$

其他的推导过程与第一题完全相同。

举例推导

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    dp[0] = []int{-prices[0], 0}
    for i := 1; i < len(prices); i++ {
        dp[i] = make([]int, 2)
        //dp[i][0]代表第i天持有股票，剩余现金，有两种情况
        //1 第i天买入，则剩余现金为第i-1天不持有的现金减去第i天买股票花费的现金
        //2 第i-1天就已经持有，则第i天与其相同
        dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0])

        //dp[i][1]代表第i天不持有股票，剩余现金，有两种情况
        //1 第i天卖出，则卖出后剩余的现金就是第i-1天持有时的剩余现金加上卖出的金额
        //2 第i-1天就已经不持有，则与其保持一致
        dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])
    }

    //最后一天不持有时的现金一定是最多的
    return dp[len(prices) - 1][1]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

买卖股票的最佳时机 3（最多只能买卖 2 次）

leetcode 123

1
2
3
4
5
6
7
8
9
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

问题分析

本题进一步增加限制，最多只能完成 $2$ 笔交易。这样就让买卖操作有了次序限制，在之前的题目中，每一个交易日只需要持有和不持有两个状态标识就可以了。但是本题中的状态就需要进一步细分。

假设我们最终进行了 $2$ 笔交易，那么每个交易日都可能存在 $5$ 种状态：

  • 从第 $1$个交易日到当前还未进行过任何操作
  • 第 $1$ 次持有：当日买入，或前一日一经处于此状态
  • 第 $1$ 次不持有：当日卖出，或前一日一经处于此状态
  • 第 $2$ 次持有：当日买入，或前一日一经处于此状态
  • 第 $2$ 次不持有：当日卖出，或前一日一经处于此状态

这样实际上跟前两题就十分类似了，只是需要将 $dp$ 数组中标记状态的第 $2$ 维数组扩容至大小为 $5$ 就可以了，省下的推导思想都是一样的

举例推导

以题目示例为例，列举推导最终结果：

结果获取

前两题中，收益最大的是在最后一个交易日不持有状态时的剩余现金。

而本题也类似，收益最大的是在最后一个交易日第二次不持有状态时的剩余现金。

golang 代码实现

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
func maxProfit(prices []int) int {
    //定义dp数组，dp[i][j]代表第i天，j状态下手中剩余的现金数，在第一次购买股票之前的现金数是0（每一个代表的是一种持续的状态，并不仅只是代表第i天）
    //dp[i][0] 没有任何操作，也就是从来都没有操作过，现金为0
    //dp[i][1] 第i天处于第一次持有状态时剩余现金数
    //dp[i][2] 第i天处于第一次卖出状态时剩余现金数
    //dp[i][3] 第i天处于第二次持有状态时剩余现金数
    //dp[i][4] 第i天处于第二次卖出状态时剩余现金数
    dp := make([][5]int, len(prices))
    //只要是买入就是 -prices[0]，第一天不可能卖出所以是0
    dp[0] = [5]int{0, -prices[0], 0, -prices[0], 0}
    for i := 1; i < len(prices); i++ {
        dp[i] = [5]int{}

        //没有操作，每一天的0位置都是一样的0值，所以可以省略
        //dp[i][0] = dp[i - 1][0]

        //第i天处于第一次持有状态
        //1 第i天买入，那么第i-1天必然是没有操作的状态，在期基础上减去第i天股票价格
        //2 第i-1天就已经是第一次持有状态，那么与其相同
        dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])

        //第i天处于第一次卖出状态
        //1 第i天卖出，那么第i-1天必然是第一次持有的状态，在其基础上增加第i天的股票价格
        //2 第i-1天就已经是第一次卖出状态，那么与其相同
        dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

        //第i天处于第二次持有状态
        //1 第i天买入，那么第i-1天必然是第一次卖出的状态，在其基础上减去第i天的股票价格
        //2 第i-1天就已经是第二次持有状态，那么与其相同
        dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])

        //第i天处于第二次卖出状态
        //1 第i天卖出，那么第i-1天必然是第二次持有的状态，在其基础上增加第i天的股票价格
        //2 第i-1天就已经是第二次卖出状态，那么与其相同
        dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])
    }

    //与前两个问题类似，剩余金额最大的必然是在第二次卖出操作之后
    return dp[len(prices) - 1][4]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

买卖股票的最佳时机 4（最多可以买卖 k 次）

leetcode 188

1
2
3
4
5
6
7
8
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

问题分析

本题与第三题基本一致，唯一的区别就在于第三题限制最多只能交易两次，而本题的交易次数根据 $k$ 值动态变化，也就是 $dp$ 数组的第二维子数组随着 $k$ 值动态变化：

1
dp[i] = make([]int, (2 * k) + 1)

$dp$​​ 数组的推导过程完全与第三题一致。

golang 代码实现

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
func maxProfit(k int, prices []int) int {
    if len(prices) <= 0 {
        return 0
    }
    //dp数组定义类似第123题，差别在于表示每一天状态的第二维数组，大小随k值动态变化
    dp := make([][]int, len(prices))
    dp[0] = make([]int, (2 * k) + 1)
    //初始化，偶数的位置都是买入（实际上都是第一次买入），那么就都是-prices[0]
    for i := 1; i < len(dp[0]); i += 2 {
        dp[0][i] = -prices[0]
    }
    //推导dp
    for i := 1; i < len(prices); i++ {
        dp[i] = make([]int, (2 * k) + 1)
        //dp[i][0]代表保持还没有任何操作的状态，所以可以不做处理
        //dp[i][0] = dp[i - 1][0]，若作处理的话那么它应该延续前一天未处理状态下的值

        //状态转移过程是个难点
        for j := 1; j <= k; j++ {
            //第j次买入对应的索引，第j卖出对应的索引就是idx+1
            idx := (j - 1) * 2 + 1
            //dp[i][奇数]位置都是代表买入（第j次买入）
            dp[i][idx] = max(dp[i - 1][idx - 1] - prices[i], dp[i - 1][idx])
            
            //dp[i][偶数]位置都是代表卖出（第j次卖出）
            dp[i][idx + 1] = max(dp[i - 1][idx] + prices[i], dp[i - 1][idx + 1]) 
        }
    }

    //同样类似第123题，剩余现金最多的就是最后一次卖出后的状态
    return dp[len(prices) - 1][2 * k]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

最佳买卖股票时机 5（可以买卖多次，每次卖出后有一天冷冻期）

leetcode 309

1
2
3
4
5
6
7
8
9
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

问题分析

本题增加了名为冷冻期的交易状态限制，也就是在股票卖出之后的一天不能买入。如果没有冷冻期这一限制，那么就是上面记录的第二题了。增加了冷冻期后，实际就是将第二题中的不持有状态进行细分（卖出和不持有中间多了一个冷冻期状态），对于每一个交易日，可能存在如下几种状态：

  • 持有
    • 当日买入
    • 前一天就已经是持有状态
  • 当日卖出
  • 冷冻期
  • 冷冻期后不持有
    • 前一天是冷冻期，当日不操作
    • 前一天就已经是冷冻期后不持有的状态

推导过程就与前面的题目一样了，结果选取最后一个交易日所有的不持有状态（当日卖出、冷冻期、冷冻期后不持有）下的剩余现金的最大值。

举例推导

golang 代码实现

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
func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    //每一个交易日有4种状态：持有、当天卖出、冷冻期、冷冻期过后继续保持不持有
    dp[0] = []int{-prices[0], 0, 0, 0}
    for i := 1; i < len(prices); i++ {
        dp[i] = make([]int, 4)
        /*
            第i天持有：可能是当天购买，也可能第i-1天就已是持有状态
                当天购买，可以从两个状态推导来：
                    第i-1天是冷冻期，则剩余现金就是i-1天处于冷冻期下剩余的现金 - 第i天的股票价格
                    第i-1天是冷冻期过后的不持有状态，则剩余现金就是i-1天冷冻期过后不持有状态下剩余的现金 - 第i天的股票价格
            第i-1天就已处于持有状态：则剩余现金与i-1天保持一致
        */
        dp[i][0] = max(max(dp[i - 1][2] - prices[i], dp[i - 1][3] - prices[i]), dp[i - 1][0])

        /*
            当天卖出：第i-1天必然持有，则剩余现金就是i-1天持有状态下剩余的现金 + 第i天的股票价格
        */
        dp[i][1] = dp[i - 1][0] + prices[i]

        /*
            第i天是冷冻期，则第i-1天必然是卖出，所以与i-1天的不持有状态保持一致
        */
        dp[i][2] = dp[i - 1][1]

        /*
            第i天是冷冻期过后的不持有
                第i-1天是冷冻期，所以与i-1天的冷冻期状态保持一致
                第i-1天就是冷冻期后的不持有状态，与其保持一致
        */
        dp[i][3] = max(dp[i - 1][2], dp[i - 1][3])
    }

    //取最后一个交易日，所有不持有股票状态下的最大值
    return max(max(dp[len(dp) - 1][1], dp[len(dp) - 1][2]), dp[len(dp) - 1][3])
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

买卖股票的最佳时机 6（可以买卖多次，每次卖出需要负手续费）

leetcode 714

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

问题分析

本题就是在第leetcode 122的基础上增加了一笔交易手续费，也就是在计算股票卖出后剩余的现金时需要减去一笔手续费 $fee$。而交易日状态分析及状态转移过程等都与 $122$ 题是完全相同的。

举例推导

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxProfit(prices []int, fee int) int {
    dp := make([][]int, len(prices))
    dp[0] = []int{-prices[0], 0}
    for i := 1; i < len(prices); i++ {
        dp[i] = make([]int, 2)
        
        //第i天持有，可能是当日买入，也可能是前一天就已经处于持有状态
        dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0])

        //第i天不持有，可能是当日卖出（卖出时需要减去一笔手续费），也可能是前一天就已经处于不持有状态
        dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1])
    }
    
    return dp[len(prices) - 1][1]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

总结

股票买卖问题的的重点在于两个方面，第一是对每个交易日可能存在的状态的定义（这也是动态规划问题的重点），不同的交易限制条件就决定了每个交易日可能存在的状态的数量；第二是对 $dp$ 数组下标的定义，本系列均定义 $dp[i][j]$ 表示第 $i$ 个交易日在 $j$ 状态下手中剩余的现金数，这是因为在购买了股票之后到卖出股票之前这段时间内的股票价格变动是不需要关心的（因为还没有卖出，没卖就没有收益，那那价格高低都无所谓），只有在卖出时用卖出的价格减去买入的价格就是本次交易的收益金额，并且我们定义了起始现金为 $0$，也就是说在第一次购买之后剩余现金就是一个负值，这也是为了方便计算股票卖出的收益（买入后剩余现金是负数，相当于记录了买入时股票的价格，在卖出时只有加上卖出时的股票价格就得到了收益）。

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

曾经是个修理工，<br>现在是一枚码农。<br>路漫漫其修远兮，<br>吾将上下而求索。<br>