【动态规划】股票买卖问题

admin 管理员组

文章数量: 887007

【动态规划】股票买卖问题

只允许买卖一次：121. 买卖股票的最佳时机 - 力扣（LeetCode） (leetcode-cn)

允许买卖两次：123. 买卖股票的最佳时机 III - 力扣（LeetCode） (leetcode-cn)

允许买卖K次：188. 买卖股票的最佳时机 IV - 力扣（LeetCode） (leetcode-cn)

允许买卖多次，不限：122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn)

考虑买卖含有手续费：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode） (leetcode-cn)

买卖含有冷冻期：309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode） (leetcode-cn)

我们从最简单的【只允许买卖1次】、【允许买卖无数次】开始思考，然后在思考有交易费、限制交易次数的复杂情况。以下，我们分别从贪心法和动态规划法来进行股票交易问题分析。

1.贪心法

1.1. 题121与题122分析

121. 买卖股票的最佳时机 - 力扣（LeetCode） (leetcode-cn)

122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn)

首先是两种简单情况：

1.只允许买卖一次：

        如果只允许买卖一次，那么如果要取得最大收益就需要在价格最低时买入，在价格最高时卖出。

2.允许买卖无数次：

        如果允许买卖无数次，那么只要后一天比前一天的价钱高就存在收益，最大收益就是所有的收益之和。

1.2. 题121和题122贪心法题解

121题题解：

遍历一次，每一天记录当前的最小值和收益最大值（当前值-当前记录的最小值），在所有记录的收益最大值中的全局最大值即为答案。

时间复杂度：O（n)

空间复杂度：O（n)

代码如下：

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""min_=prices[0]profits=[]for p in prices:min_=p if p<min_ else min_profits.append(p-min_)return max(profits)

121题题解：

允许买卖无数次（122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn)）：在每一天都看是否比前一天价格更高，高则可卖出，加上收益，最后最大收益是每次买卖的收益之和。

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""res=0pre=prices[0]for n in prices[1:]:if pre<n:res+=n-prepre=nreturn res

允许买卖一次和允许买卖无数次都可以用贪心法很简单的解决。其他问题包括只允许进行买卖有限次(2...K)、有冷静期、有手续费，这些情况用贪心法会变得复杂，所以使用动态规划法来尝试推导一般形式。

1.3.有手续费情况【题714】

        允许无限次操作的时候，我们总是想【能赚钱的时候就一定要赚钱】，也就是股票涨涨跌跌，每次涨的时候我们都获得了收益。

        假设，我们的买卖操作可以反悔。

        与没有手续费的情况不同的是，该题这里的交易是有成本的。

买入成本：buy=prices[i]+fee

1.找目前可见的最便宜的一天买入股票

2.如果今天能获得收益，先卖出，如果明天还能获得收益，那么我们就反悔，昨天卖出改为今天卖出。

class Solution(object):def maxProfit(self, prices, fee):""":type prices: List[int]:type fee: int:rtype: int"""#成本buy=prices[0]+feeres=0for p in prices[1:]:#1.找目前可见的最便宜的一天买入股票if p+fee<buy:buy=p+fee#2.如果今天能获得收益，先卖出，如果明天还能获得收益，那么我们就反悔，昨天卖出改为今天卖出。if p>buy:res+=p-buybuy=preturn res

2.动态规划法

考虑可以买卖有限次K次：

• K=无限--买卖无限次
• K=1--买卖一次
• K=2--买卖两次
• K=...

我理解动态规划是用一个数组把所有状态变化下的情况存在表里从而求解的，最重要的是找到状态转换方程。每一天都分为【有股票】和【无股票】两种情况，每天都可以进行三种行为：买入、卖出、不买不卖。

2.1.只考虑买卖的【题121和题122】的一般形式化

无股票：MP[i][0]=max{MP[i-1][0](前一天没股票，今天不买不卖),

                                MP[i-1][1]+a[i](前一天有股票，今天卖出-->无股票）}

有股票：MP[i][1]=max{ MP[i-1][0]-a[i](前一天没股票，今天买入),

                                MP[i-1][1](前一天有股票，今天不买不卖）}

2.2.只允许买卖K次【题123和题188】

加上只许买卖K次的约束，在卖出是记录交易一次：

无股票：MP[i][k][0]=max{MP[i-1][k][0](前一天没股票，今天不买不卖),

                                MP[i-1][k-1][1]+a[i](前一天有股票(已交易K-1次，今天卖出（第k次交易）-->无股票）}

有股票：MP[i][k][1]=max{ MP[i-1][k][0]-a[i](前一天没股票，今天买入),

                                MP[i-1][k][1](前一天有股票，今天不买不卖）}

最后的return值：max(MP[i-1][:][0])

但直接这么实现，三维数组容易超出题目的存储要求，时间复杂度和空间复杂度都是O（n*k*m)

2.3.存在交易费的约束【题714】

无股票：MP[i][0]=max{MP[i-1][0](前一天没股票，今天不买不卖),

                                MP[i-1][1]+a[i]-fee(前一天有股票，今天卖出-->无股票）}

有股票：MP[i][1]=max{ MP[i-1][0]-a[i](前一天没股票，今天买入),

                                MP[i-1][1](前一天有股票，今天不买不卖）}

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode） (leetcode-cn)

代码如下：

class Solution(object):def maxProfit(self, prices, fee):""":type prices: List[int]:type fee: int:rtype: int"""MP=[[0,0] for _ in prices]MP[0][0],MP[0][1]=0,-prices[0]for i in range(1,len(prices)):MP[i][0]=max(MP[i-1][0],MP[i-1][1]+prices[i]-fee)MP[i][1]=max(MP[i-1][1],MP[i-1][0]-prices[i])return MP[len(prices)-1][0]

2.4.含有冷静期(1天)【题309】

有股票：

MP[i][0]=max{MP[i-1][0](前一天有股票),MP[i-1][1]-a[i](前一天没股票但不在冷静期)}

没股票，且不在冷静期：

MP[i][1]=max{​MP[i-1][1](前一天没股票且不在冷静期),

                        MP[i-1][2](前一天没股票且在冷静期)}

没股票，且在冷静期：

MP[i][2]=MP[i-1][0]+a[i](把股票在今天卖出，所以进入了冷静期）

代码如下：

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""MP=[[0,0,0] for _ in prices]MP[0]=[-prices[0],0,0]for i in range(1,len(prices)):MP[i][0]=max(MP[i-1][0],MP[i-1][1]-prices[i])MP[i][1]=max(MP[i-1][1],MP[i-1][2])MP[i][2]=MP[i-1][0]+prices[i]return max(MP[len(prices)-1][1],MP[len(prices)-1][2])

3.优化动态规划法解决题123和题188

        约束只交易两次和只交易K次的两题，状态空间在三维则容易超出内存限制。

        在第二部分进行推导时，将所有状态都放在了一个三维数组中，buy和sell也可以拆开进行表示。第i个状态每次之和前一个i-1状态相关，故而可以优化存储。

3.1.只允许交易两次【题123】

买卖股票的最佳时机 III - 买卖股票的最佳时机 III - 力扣（LeetCode） (leetcode-cn)

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""buy1,buy2=-prices[0],-prices[0]sell1,sell2=0,0for p in prices:buy1=max(buy1,-p)sell1=max(sell1,buy1+p)buy2=max(buy2,sell1-p)sell2=max(sell2,buy2+p)return sell2

3.2.扩展到K次【题188】

引申到K次：买卖股票的最佳时机 IV - 买卖股票的最佳时机 IV - 力扣（LeetCode） (leetcode-cn)

需要注意的是，可以买卖K次，那么有[0,k]（左右闭区间）这些状态。

class Solution(object):def maxProfit(self, k, prices):""":type k: int:type prices: List[int]:rtype: int"""if prices==[] or k==0:return 0dp=[[[0,-prices[0]] for __ in range(k+1)] for _ in prices]for i in range(len(prices)):dp[i][0][1]=float("-inf")for i in range(len(prices)):for j in range(1,k+1):dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])return dp[len(prices)-1][k][0]

本文标签： 动态规划股票买卖问题