算法训练Day50 | LeetCode123. 买卖股票的最佳时机III(最多买卖2次);LeetCode188. 买卖股票的最佳时机IV(最多买卖K次)

发布于:2022-11-09 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

LeetCode123. 买卖股票的最佳时机III

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

LeetCode188. 买卖股票的最佳时机IV 

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获


LeetCode123. 买卖股票的最佳时机III

链接: 链接:123. 买卖股票的最佳时机 III - 力扣(LeetCode)

1. 思路

本题相对于LeetCode121和LeetCode122难了不少;关键在于至多买卖两次,这意味着可以买卖一次,可以买卖两次,也可以不买卖。

接来下我用动态规划五部曲详细分析一下:

1.1 确定dp数组以及下标的含义

一天一共就有五个状态,

  1. 没有操作
  2. 第一次买入的状态
  3. 第一次卖出的状态
  4. 第二次买入的状态
  5. 第二次卖出的状态

dp[i][j]中 i表示第i天,j为 [0 - 4] 五个状态,dp[i][j]表示第i天状态j所剩最大现金;

1.2 确定递推公式

需要注意:dp[i][1],表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,这是很多同学容易陷入的误区;

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i],还是dp[i - 1][1]呢?

一定是选最大的,所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分:

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

1.3 dp数组初始化

  • dp[0][0]

    第0天没有操作,这个最容易想到,就是0,即:dp[0][0] = 0;

  • dp[0][1]

    第0天做第一次买入的操作,dp[0][1] = -prices[0];

  • dp[0][2]

    第0天做第一次卖出的操作,这个初始值应该是多少呢?首先卖出的操作一定是收获利润,整个股票买卖最差情况也就是没有盈利即全程无操作现金为0,从递推公式中可以看出每次是取最大值,那么既然是收获利润如果比0还小了就没有必要收获这个利润了,所以dp[0][2] = 0;(这个解释我不是很懂)我认为可以理解成第0天买入了再卖出,价格是一样的,所以为0;

  • dp[0][3]

    第0天第二次买入操作,初始值应该是多少呢?应该不少同学疑惑,第一次还没买入呢,怎么初始化第二次买入呢?

    第二次买入依赖于第一次卖出的状态,其实相当于第0天第一次买入了,第一次卖出了,然后在买入一次(第二次买入),那么现在手头上没有现金,只要买入,现金就做相应的减少。所以第二次买入操作,初始化为:dp[0][3] = -prices[0];

  • dp[0][4]

    可以理解为第0天完成了第一次买入,卖出,又第二次买入,卖出,总体来说利润为0;同理第二次卖出初始化dp[0][4] = 0;

1.4 确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值;

1.5 举例推导dp数组

以输入[1,2,3,4,5]为例

大家可以看到红色框为最后两次卖出的状态。

现在最大的时候一定是卖出的状态,而两次卖出的状态现金最大一定是最后一次卖出。所以最终最大利润是dp[4][4];

因为是最大的利润,不会小于第一次卖出的利润,因为大不了就day5的时候,再在同一天买进卖出,j=2的利润就等于j=4的利润率了,所以可以直接取最右下角的数即可;

2. 代码实现

# 动态规划
# time:O(N);space:O(N)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp的定义
        # j 为五种状态 
        # 0: 无操作
        # 1: 1st 买入
        # 2: 1st 卖出
        # 3: 2nd 买入
        # 4: 2nd 卖出
        # dp[i][j] 第i天,在j状态的最大金钱余额
        length = len(prices)
        dp = [[0]*5 for _ in range(length)]
        # 初始化
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[0][2] = 0
        dp[0][3] = -prices[0]
        dp[0][4] = 0
        # 遍历
        for i in range(1,length):
            # 递推公式
            dp[i][0] = dp[i-1][0]
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
            dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])
            dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])
            dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])
        return dp[length-1][4]

3. 复杂度分析

  • 时间复杂度:O(N)

    N为prices数组的长度;需要从头到尾遍历prices数组一遍;

  • 空间复杂度:O(N)

    dp数组的大小为N*5,整体来说还是O(N)的复杂度;

4. 思考与收获

  1. (二刷再考虑看不看)还有一种优化空间的写法

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) == 0:
                return 0
            dp = [0] * 5
            dp[1] = -prices[0]
            dp[3] = -prices[0]
            for i in range(1, len(prices)):
                dp[1] = max(dp[1], dp[0] - prices[i])
                dp[2] = max(dp[2], dp[1] + prices[i])
                dp[3] = max(dp[3], dp[2] - prices[i])
                dp[4] = max(dp[4], dp[3] + prices[i])
            return dp[4]
    
    
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    大家会发现dp[2]利用的是当天的dp[1]。 但结果也是对的;我来简单解释一下:dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1],即保持买入股票的状态,那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。

    如果dp[1]取dp[0] - prices[i],今天买入股票,那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是尽在再卖出股票,一买一卖收益为0,对所得现金没有影响。相当于今天买入股票又卖出股票,等于没有操作,保持昨天卖出股票的状态了。这种写法看上去简单,其实思路很绕,不建议大家这么写,这么思考,很容易把自己绕进去!对于本题,把版本一的写法研究明白,足以!

    Reference:代码随想录 (programmercarl.com)

    本题学习时间:60分钟。


LeetCode188. 买卖股票的最佳时机IV 

链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)

1. 思路

本题可以说是LeetCode123.买卖股票的最佳时机III的进阶版,这里要求至多有K次交易;动态规划五部曲分析如下:

1.1 确定dp数组以及下标的含义

在LeetCode123.买卖股票的最佳时机III中,定义了一个二维的dp数组,题其实依然可以用一个二维dp数组;使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j];

j的状态表示为:

  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出
  • .....

大家应该发现规律了吧 ,除了0以外,偶数就是卖出,奇数就是买入

题目要求是至多有K笔交易,那么j的范围就定义为 2 * k + 1 就可以了。

1.2 确定递推公式

还要强调一下:dp[i][1],表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,这是很多同学容易陷入的误区;

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i - 1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]

选最大的,所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可以类比剩下的状态,代码如下:

for j in range(0, 2*k-1, 2):
      dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
      dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])

本题和动态规划:123.买卖股票的最佳时机III (opens new window)最大的区别就是这里要类比j为奇数是买,偶数是卖的状态;

1.3 dp数组初始化

第0天没有操作,这个最容易想到,就是0,即:dp[0][0] = 0;

第0天做第一次买入的操作,dp[0][1] = -prices[0];

第0天做第一次卖出的操作,这个初始值应该是多少呢?

首先卖出的操作一定是收获利润,整个股票买卖最差情况也就是没有盈利即全程无操作现金为0,

从递推公式中可以看出每次是取最大值,那么既然是收获利润如果比0还小了就没有必要收获这个利润了。

所以dp[0][2] = 0;

第0天第二次买入操作,初始值应该是多少呢?

不用管第几次,现在手头上没有现金,只要买入,现金就做相应的减少。

第二次买入操作,初始化为:dp[0][3] = -prices[0];

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

代码如下:

for j in range(1, 2*k, 2):
      dp[0][j] = -prices[0]

在初始化的地方同样要类比j为偶数是卖、奇数是买的状态;

1.4 确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值;

1.5 举例推导dp数组

以输入[1,2,3,4,5],k=2为例;

最后一次卖出,一定是利润最大的,dp[prices.size() - 1][2 * k]即红色部分就是最后求解。

2. 代码实现

# 动态规划
# time:O(N*K);space:O(N*K)
class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        # 排除base case
        if len(prices) == 0: return 0
        length = len(prices)
        # 初始化,有length行,2K+1列
        dp = [[0]*(2*k+1) for _ in range(length)]
        # j 为奇数的地方,代表买入,全部初始化为-prices[0]
        for j in range(2*k):
            if j%2:  dp[0][j] = -prices[0]
        # 从i=1,第一天开始遍历
        for i in range(1,length):
            # j 需要遍历2K个状态
            for j in range(1,2*k+1):
                # 如果j为奇数,代表是买入日
                if j%2:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                # 如果j为偶数,代表是卖出日
                if j%2 == 0:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i])
        return dp[length-1][2*k]

3. 复杂度分析

  • 时间复杂度:O(N*K)

    其中N为prices数组的长度,K为题目中给的最多买卖K次;for loop中需要循环N *(2K)次;

  • 空间复杂度:O(N*K)

    其中N为prices数组的长度,K为题目中给的最多买卖K次;dp数组的大小为N*(2K+1)

4. 思考与收获

  1. 有的解法是定义一个三维数组dp[i][j][k],第i天,第j次买卖,k表示买还是卖的状态,从定义上来讲是比较直观;但感觉三维数组操作起来有些麻烦,这里直接用二维数组来模拟三维数组的情况,代码看起来也清爽一些;

  2. (二刷再考虑看不看)类似LeetCode123 ,还有一种状态压缩的写法如下:

    class Solution:
        def maxProfit(self, k: int, prices: List[int]) -> int:
            if len(prices) == 0: return 0
            dp = [0] * (2*k + 1)
            for i in range(1,2*k,2):
                dp[i] = -prices[0]
            for i in range(1,len(prices)):
                for j in range(1,2*k + 1):
                    if j % 2:
                        dp[j] = max(dp[j],dp[j-1]-prices[i])
                    else:
                        dp[j] = max(dp[j],dp[j-1]+prices[i])
            return dp[2*k]
    
    

Reference:代码随想录 (programmercarl.com)

本题学习时间:80分钟。


本篇学习时间约2小时,总结字数5000+;又学习了动态规划中股票问题的两个题目,难度比之前的股票问题大了不少,IV是III的进阶版,推广到最多买卖K次了。(求推荐!)