QingZhi's Blog

Persistence is not easy

0%

动态规划——股票专题解法

Posted on In , Views: Valine:

我自己对股票问题经常打怵，特将相关算法框架与相关题目解读总结如下：

参考Leetcode解释

前言

像动态规划的思想我之前是有总结过的，但是在应用方面还是很薄弱。我个人并不认为是理论的不清晰，更多的情况是由于状态的定义以及状态转移方程推导这两方面的问题，甚至有时需要将状态转移方程转换为递推式才能够更好的解决问题。

动态规划之穷举

不管是动态规划也好，贪心算法也罢，其实都是解决某类问题的策略，其均是在所有的可能性中探索自己的答案，并快速得到你想要的结果。穷举法是最为简单而暴力的解法，但是其平铺直述的将所有的状态展现了出来。有必要了解下股票问题的穷举法。

解答人在这里采用了状态来进行穷举，具体到每一天，观察存在哪几种状态，并找出每个状态对应的选择。如下所示：

1
2
3
4
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

上面的伪代码中展示的就是利用状态进行穷举的形式。那么股票问题中我们的状态有哪些呢？

  1. 日期:T
  2. 交易次数:K
  3. 是否持有股票:1，持有； 0，不持有。

选择又有哪些呢？1.买入 2，卖出 3.不做动作。分别用buy,sell,rest表示前面的三种选择。但是在股票问题中并不是每一天你都可以任意进行选择，其存在某种限制：buy必须在sell后，sell必须在buy后，rest操作还取决于前一天是buy OR sell等等。选择往往由题意进行限制。

我们不去管什么限制，仅仅是穷举出来的形式如下：

1
2
3
4
5
6
7
8
9
10
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
#n 为天数，大 K 为最多交易数
#此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)
#比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易

我们的想要的答案是：$dp[n-1][K][0]$ , 即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 $dp[n - 1][K][1]$？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

状态转移框架

上面的穷举中其实已经暗含将问题整个状态定义为：dp[i] [w] [j] 表示第 i 天，在交易次数限制在 w 的情况下，是否持有时所能带来的最大利润。

我们接下来思考状态之间到底是如何转移的呢？

根据选择进行转移，我们以从是否持有状态出发，如图：

根据上图我们可以写出状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k][1] + price[i] )
#		      max( 做出rest选择 ， 做出sell选择 )
#解释：今天我没有持有股票，有两种可能：
#要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
#要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。



dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0] - price[i] )
#			 max( rest , buy )
#解释：今天我持有着股票，有两种可能：
#要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
#要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

边界情况

1
2
3
4
5
6
7
8
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

其实上面的边界，这么写起来是很别扭的，我们可以理解为综合考虑：i , k极端情况下的的边界分布。

以上三部分其实就是讲解了：状态、状态转移方程、边界。相当于提出了一套用于解决股票问题的框架。

应用

leetcode_0121

题目描述：

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

交易次数仅限于一次,k=1

状态定义： $dp[i][k][j] , 0 < i < len(prices) , 0<=k<=1$ 表示第 i 天 ，第 K 次交易 ， 持有或不持有，所能获得的最大利润，0 < i < len(prices) , 0<=k<=1

状态转移方程: 

1
2
3
4
5
6
7
dp[i][1][1] = max( dp[i-1][1][1], dp[i-1][0][0] - price[i] )
# 第 i 天的状态为1（持有）时，交易一定出现过，k=1(题目限制只能1次)：昨天已经持有，今天选择观望，或者昨天不曾持有，今天选择买入
# dp[i-1][0][0] 在这道题目中一定为0，故应该为
# PS 如果代码仍然按照第一行编写，便会出现错误的结果，所以状态转移方程也根据题目存在差异，框架仅用于切入点。
dp[i][1][1] = max( dp[i-1][1][1],  - price[i] )
dp[i][1][0] = max( dp[i-1][1][0] ,dp[i-1][1][1] + price[i] )
# 第 i 天状态为0（不持有）时，交易已经出现，k=1(题目限制只能1次)：昨天未持有，今天选择观望，或者昨天还是持有的，今天选择卖出
  • 为什么上面没有考虑$dp[i][0][0]$ 这是由于未曾发生交易，这是边界情况，不需要转移好嘛。

由于限制交易次数为1次：状态转移方程等式左侧K均为1，这说明去掉K也是不影响的。

这里的解释很牵强，我倒认为是由于持有与不持有本身就已经代表是否发生了一次交易，这导致这道题不考虑K也是可以的。

边界转移方程优化：

1
2
3
4
dp[i][1] = max( dp[i-1][1],  - price[i] )
#第 i 天已经持有了，那么i-1天已持有，今天观望，或者，i-1 天未持有，今天买入
dp[i][0] = max( dp[i-1][0] ,dp[i-1][1] + price[i] )
#第 i 天不再持有了，那么i-1天已不再持有，今天观望，或者，i-1 天持有，今天卖出

边界方程：

1
2
3
dp[-1][0] = 0
dp[-1][1] = float("-inf")
# 这里的-1虽然代表数组下标，表示尚未开始时的状态，但是-1本身是不合理的，我们一般会特殊处理即可。

算法代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp table初始化
        dp = [ [0 for _ in range(2)] for _ in range(len(prices)+1)]
        #边界表示第0天的状况
        dp[0][0] = 0
        dp[0][1] = float("-inf")
        for i in range(1, len(prices)+1):
            dp[i][1] = max( dp[i-1][1],  - prices[i-1] )
            dp[i][0] = max( dp[i-1][0] ,dp[i-1][1] + prices[i-1] )
        return dp[-1][0]

算法分析：

  • 时间复杂度：一次迭代完成，$O(n)$
  • 空间复杂度：需要一个数组，$ O(n) $

leetcode_0122

题目描述

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
Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
 

Constraints:

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

题目中的交易次数是没有限制的。

状态定义： $dp[i][k][j] , 0 < i < len(prices) , 0<=k<float(“inf”)$ 表示第 i 天 ，第 K 次交易 ， 持有或不持有，所能获得的最大利润

没有变化

状态转移方程：

1
2
3
4
dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0] - prices[i] ) 
#第 i 天 k 次交易 持有状态 = max( 第 i-1 天 k 次交易 持有状态，选择观望 , 第 i-1 天 k-1 次交易 未持有状态，选择买入 )
dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k-1][1] + prices[i] )
#第 i 天 k 次交易 未持有状态 = max( 第 i-1 天 k 次交易 未持有状态，选择观望 , 第 i-1 天 k-1 次交易 持有状态，选择卖出 )

由于题目中不对 K 有任何限制,那么，K的范围就是到无穷大，那么k与k-1的变化是毫无意义的，我们根本不关注到底发生了多少次，故状态转移方程修改如下：

1
2
3
4
dp[i][1] = max( dp[i-1][1] , dp[i-1][0] - prices[i] ) 
#第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )
dp[i][0] = max( dp[i-1][0] , dp[i-1][1] + prices[i] )
#第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天 持有状态，选择卖出 )

边界方程：

1
2
dp[-1][0] = 0
dp[-1][1] = float("-inf")

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0 for _ in range(2)] for _ in range(len(prices)+1)]
        dp[0][0] = 0
        dp[0][1] = float("-inf")

        for i in range(1,len(prices)+1):
            dp[i][1] = max( dp[i-1][1] , dp[i-1][0] - prices[i-1] ) 
			#第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )
            dp[i][0] = max( dp[i-1][0] , dp[i-1][1] + prices[i-1] )
			#第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天 持有状态，选择卖出 )
        return dp[-1][0]

算法分析

同上

leetcode_0123

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

K限制在两次以内

状态定义：$dp[i][k][j] , 0 < i < len(prices) , 0<=k<=2$

状态转移方程：

1
2
3
4
dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0] - prices[i] ) 
            #第 i 天 k 次交易 持有状态 = max( 第 i-1 天 k 次交易 持有状态，选择观望 , 第 i-1 天 k-1 次交易 未持有状态，选择买入 )
dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k][1] + prices[i] )
            #第 i 天 k 次交易 未持有状态 = max( 第 i-1 天 k 次交易 未持有状态，选择观望 , 第 i-1 天 k-1 次交易 持有状态，选择卖出 )

很明显，这次状态转移方程没办法优化。

边界：

1
2
3
4
dp[-1][k][0] = 0
dp[-1][k][1] = float("-inf")
dp[i][0][0] = 0
dp[i][0][1] = float("-inf")

算法代码

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
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(len(prices)+1)]
        # 边界初始化
        for k in range(3):
            dp[0][k][0] = 0
            dp[0][k][1] = float("-inf")
        for i in range(len(prices)+1):
            dp[i][0][0] = 0
            dp[i][0][1] = float("-inf")
        #迭代过程
        for i in range(1,len(prices)+1):
            #其实这里可以采用 for k in range(3,0,-1)
            # 他人的写法
            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i-1])
            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i-1])
            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i-1])
            dp[i][1][1] = max(dp[i-1][1][1], -prices[i-1])    
        # 最大利润寻找
        maxprofit = 0
        for k in range(3):
            temp = max(dp[-1][k])
            if maxprofit < temp:
                maxprofit = temp
        return maxprofit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 迭代逻辑部分，有所更改，用了双循环
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(len(prices)+1)]
        for k in range(3):
            dp[0][k][0] = 0
            dp[0][k][1] = float("-inf")
        for i in range(len(prices)+1):
            dp[i][0][0] = 0
            dp[i][0][1] = float("-inf")
        for i in range(1,len(prices)+1):
            # 注意K的取值也是从小到大的
            for k in range(1,3):
                dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0] - prices[i-1] ) 
            #第 i 天 k 次交易 持有状态 = max( 第 i-1 天 k 次交易 持有状态，选择观望 , 第 i-1 天 k-1 次交易 未持有状态，选择买入 )
                dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k][1] + prices[i-1] )
            #第 i 天 k 次交易 未持有状态 = max( 第 i-1 天 k 次交易 未持有状态，选择观望 , 第 i-1 天 k-1 次交易 持有状态，选择卖出 )
        maxprofit = 0
        for k in range(3):
            temp = max(dp[-1][k])
            if maxprofit < temp:
                maxprofit = temp
        return maxprofit

算法分析：

leetcode_0124

K没有限制，就是上一题的扩展，这里不做任何解释

算法代码

超出时间限制，暂时不想优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:

        dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(len(prices)+1)]
        for k in range(k+1):
            dp[0][k][0] = 0
            dp[0][k][1] = float("-inf")
        for i in range(len(prices)+1):
            dp[i][0][0] = 0
            dp[i][0][1] = float("-inf")
        for i in range(1,len(prices)+1):
            for k in range(1,k+1):
                
                dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0] - prices[i-1] ) 
            #第 i 天 k 次交易 持有状态 = max( 第 i-1 天 k 次交易 持有状态，选择观望 , 第 i-1 天 k-1 次交易 未持有状态，选择买入 )
                dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k][1] + prices[i-1] )
            #第 i 天 k 次交易 未持有状态 = max( 第 i-1 天 k 次交易 未持有状态，选择观望 , 第 i-1 天 k-1 次交易 持有状态，选择卖出 )
        maxprofit = 0
        for k in range(k+1):
            temp = max(dp[-1][k])
            if maxprofit < temp:
                maxprofit = temp
        return maxprofit

leetcode_0309

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

状态定义： $dp[i][k][j] , 0 < i < len(prices) , 0<=k<float(“inf”)$ 表示第 i 天 ，第 K 次交易 ， 持有或不持有，所能获得的最大利润

状态转移方程：很明显，并不需要记录K值

1
2
3
4
dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i])
#  第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天持有状态，选择卖出 )
dp[i][1] = max(dp[i-1][1] , dp[i-2][0] - prices[i])
#  第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )

边界方程：

1
2
dp[-1][0] = 0
dp[-1][1] = float("-inf")

算法代码

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:
        dp = [[0 for _ in range(2)] for _ in range(len(prices)+1)]
        dp[0][0] = 0
        dp[0][1] = float("-inf")

        for i in range(1,len(prices)+1):
            # 这里这么处理仅仅是处理一开始不愿意初始化罢了，一开始是没有前天的好嘛，我们的数组只虚拟了一天，也就是dp[0]这一天
            if i == 1:
                dp[i][1] = max( dp[i-1][1] , dp[i-1][0] - prices[i-1] )
            else:
                dp[i][1] = max( dp[i-1][1] , dp[i-2][0] - prices[i-1] ) 
			#第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )
            dp[i][0] = max( dp[i-1][0] , dp[i-1][1] + prices[i-1] )
			#第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天 持有状态，选择卖出 )
        return dp[-1][0]

算法分析

leetcode_0714

状态定义：什么的都与0122题一摸一样

状态转移方程：

1
2
3
4
5
# 卖出的时候扣除费用就好 
dp[i][1] = max( dp[i-1][1] , dp[i-1][0] - prices[i-1] ) 
#第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )
dp[i][0] = max( dp[i-1][0] , dp[i-1][1] + prices[i-1] - fee )
#第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天 持有状态，选择卖出,并扣除费用 )

边界：一样

算法代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp = [[0 for _ in range(2)] for _ in range(len(prices)+1)]
        dp[0][0] = 0
        dp[0][1] = float("-inf")
        for i in range(1,len(prices)+1):
            dp[i][1] = max( dp[i-1][1] , dp[i-1][0] - prices[i-1] ) 
			#第 i 天 持有状态 = max( 第 i-1 天 持有状态，选择观望 , 第 i-1 天 未持有状态，选择买入 )
            dp[i][0] = max( dp[i-1][0] , dp[i-1][1] + prices[i-1] - fee )
			#第 i 天 未持有状态 = max( 第 i-1 天 未持有状态，选择观望 , 第 i-1 天 持有状态，选择卖出,并扣除费用 )
        return dp[-1][0]

算法分析