目录

Leetcode买卖股票题

题记

leetcode上刷动态规划有几道股票题,索性就一起刷了。

题目

121 买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

只是一道动态规划的简单题,在之前的博客里总结过了。

状态转移方程,可以看到前i天:image-20200917142521944

123 买卖股票的最佳时机 III

image-20200930195940421

与121的区别在于最多可以完成2次交易,就让简单题变成了困难题。

最开始的思路就是遇到降了就卖,最后做一个排序,比如131419,获得收益是2、3、8,排完序之后求最大的两个3、8之和,但是这样解决不了132719,因为这样得到是2、5、8,排序相加结果是13,但是实际上1买7卖收益最大,结果是6+8=14。

没想通,直接看题解了。

定义二维数组 dp[n][4]这的n表示天数,4表示4种不同的状态:

dp1[i][0]:第一次买入;

dp2[i][1]:第一次卖出;

dp3[i][2]:第二次买入;

dp4[i][3]:第二次卖出。

第一次买卖:

第一次买入:第一次买入后保持不动, 或者从初始状态转换而来 dp[i][0] = max(dp[i-1][0], -prices[i])

第一次卖出:第一次卖出后保持不动,或者从第一次买入转换而来 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] -prices[i])

第二次卖出:第二次卖出后保持不动,或者从第二次买入转换而来 dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i])

132719的状态如下表所示,不加粗表示保持不动,加粗表示对当前天进行了买卖操作。

day1 day2 day3 day4 day5 day6
1 3 2 7 1 9
第一次买 -1 -1 -1 -1 -1 -1
第一次卖 0 2 2 6 6 8
第二次买 -1 -1 0 0 5 5
第二次卖 0 2 2 2 2 14
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        days = len(prices)
        dp = [[0] * 4 for _ in range(days)]
        dp[0][0] = -prices[0] # 第一天第一次买入
        dp[0][2] = -prices[0] # 第一天第二次买入
        for i in range(1, days):
            # 第一次买入卖出
            dp[i][0] = max(dp[i-1][0], -prices[i])
            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])
        return max(0, dp[-1][0], dp[-1][3])

由于第i天只依赖于第i-1天,所以可以优化:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        days = len(prices)
        dp1 = 0
        dp3 = 0
        
        dp0 = -prices[0] # 第一天第一次买入
        dp2 = -prices[0] # 第一天第二次买入
        for i in range(1, days):
            # 第一次买入卖出
            dp0 = max(dp0, -prices[i])
            dp1 = max(dp1, dp0 + prices[i]) # 实际上这一行放在上上行更好理解
            # 第二次买入卖出
            dp2 = max(dp2, dp1 - prices[i])
            dp3 = max(dp3, dp2 + prices[i])
        return max(dp1, dp3)

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

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

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

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

和123题思路完全一样,但是要加上一个对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
29
30
31
32
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) <= 1 or k<=0:
            return 0
        days = len(prices)

        # 当k非常大时转为无限次交易,否则会造成Memory Error
        if k > days//2:
            dp0, dp1 = 0, -prices[0]
            for i in range(1, days):
                dp0 = max(dp0, dp1+prices[i])
                dp1 = max(dp1, dp0-prices[i])
            return max(dp0, dp1)

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

            # dp[3] = max(dp[3], dp[2] + prices[i])
            # dp[2] = max(dp[2], dp[1] - prices[i])
            #
            # dp[4] = max(dp[4], dp[3]+prices[i])
            # dp[3] = max(dp[3], dp[2]-prices[i])
            for j in range(k-1):
                dp[2*j+3] = max(dp[2*j+3], dp[2*j+2] + prices[i])
                dp[2*j+2] = max(dp[2*j+2], dp[2*j+1] - prices[i])
            # print(dp)
        return max(dp)