@Author：Runsen

@Date：2020/09/26

悄然间时间来到十月，不禁感慨，过去的这一个月浪的‘无知’，我其实是一个很没有原则的人，做的很多事情都是随心所欲，骨子里放纵不羁爱自由。可能是最后一年的时间了吧，自己在学业上没有了太多心劲，抱着一种‘再不疯狂就老了’的心态开始游戏人生，放纵自我，或许没有那么严重，但确实实实在在的放飞自我了。

还有一个关键原因是每次想到自己专业都会一阵心痛，宿舍成天游戏，我还要为补考和知行分焦虑，这世间我仿佛觉得大一自己入IT的门，但又不是自己的专业，都是凭自己一天一天积累而来。毕业却为毕业证而焦虑的恐慌，学分绩点1.47，专业排名倒数第七，我哪里差了？都不知道我大学这么努力，还要给人看死。

不说了。赶紧开干Leetcode的股票系列。前面都是发牢骚！自己不满足自己的现状而已！

在极客时间中，我知道动态规划必须要面对股票系列，背包系列差不多了，那就上吧。

买卖股票的最佳时机（买一次）

这是Leetcode的第121题： 买卖股票的最佳时机（买一次）

题目不说了，就是只能买一次，

class Solution: def maxProfit(self, prices: List[int]) -> int: # dp的状态转移方程：dp[i] = max(dp[i-1],prices[i]-minprice) n = len(prices) if n == 0: return 0 dp = [0] * n minprice = prices[0] for i in range(1,n): minprice = min(minprice,prices[i]) dp[i] = max(dp[i-1],prices[i]-minprice) return dp[-1]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

买卖股票的最佳时机（买N次）

这是Leetcode的第122题： 买卖股票的最佳时机（买N次）

那么dp就需要开一个维度来表示当天是买还是卖。

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' 可以买卖多次 dp[i][j] dp[i][0] 表示前 i天的最大利润，第i天不买，那么dp转移方程取决于i-1天是有股票还是没有股票 dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1] 表示前 i天的最大利润，第i天必须买, 那么dp转移方程取决于i-1天是有股票还是没有股票 dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]) ''' n = len(prices) if n == 0: return 0 dp = [[0]*2 for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1,n): dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]) return dp[-1][0] # 找到所有的上升区间，计算每个上升区间的价格差,直接节约了空间复杂度 为O(1) # 贪心做法 n = len(prices) profit = 0 if n == 0 : return 0 for i in range(1,n): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit # 最好的做法就是有一个变量储存没有股票的最大利润和有股票的最大利润，然后不断地维护
		# cash表示第i天结束，没有股票的最大利润 # hold表示第i天结束，有股票的最大利润 cash, hold = 0, -prices[0] for i in range(1,len(prices)): cash = max(cash,hold+prices[i]) hold = max(hold,cash-prices[i]) return cash

  

 

  
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
 

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

这是Leetcode的第123题： 买卖股票的最佳时机（买2次）

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' dp[i][k][XX]  i 表示第i的最大利润，k表示第i天之前你买了多少次，X表示第i天是否有股票 0 ,1 p[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) ''' if not prices: return 0 n = len(prices) # 初始化状态 dp = [[[0]*2 for _ in range(3)] for _ in range(n)] for k in range(3): # 第一天买入股票 dp[0][k][1] = -prices[0] # 从 i=1 处开始迭代 for i in range(1, n): for k in range(1, 3): dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) return dp[-1][2][0]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

买卖股票的最佳时机（买k次）

这是Leetcode的第188题： 买卖股票的最佳时机（买k次）

注释写得很详细了。

class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: # @Author：Runsen #dp[i][j][0] 今天是第i天 进行 j次 交易 手上没有股票 #dp[i][j][1] 今天是第i天 进行 j次 交易 手上有股票 if k == 0 or len(prices) < 2: return 0 n = len(prices) res = [] # 如果k的次数大于n//2，那么就是直接计算利润，第一天买，第二天就卖，然后第二天在买。 if k > n // 2: max_profit = 0 for i in range(1,n): profit = prices[i] - prices[i - 1] # 如果第二天比第一天高，那就直接加入 if profit > 0: max_profit += profit return max_profit # 下面就是Leetcode第123的代码 dp[i][j][0] dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)] for i in range(k + 1): # 第一天买入股票 dp[0][i][1] = - prices[0] for i in range(1, n): for k in range(1, k+1): dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) # 求dp[i][k][0] 的最大，这里我直接开数组 for m in range(k + 1): res.append(dp[-1][m][0]) return max(res)

  

 

  
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
 

买卖股票的最佳时机（买N次加CD冷却时间）

这是Leetcode的第309题： 买卖股票的最佳时机（买N次加CD冷却时间）

注释写得很详细了。

class Solution: def maxProfit(self, prices: List[int]) -> int: # 如果设置dp的状态？ 就是关键。冷冻期其实就是CD技能的时间。 # dp[i][0]表示第i天结束之后，我有股票的最大收益。那么有可能i-1天我本来就有股票，今天的价不好，我不卖了，或者昨天我没有股票，但我今天可以买了股票，说明今天不是冷冻期。 # dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) # dp[i][1]表示第i天结束之后，我没有股票，明天就是冷冻期，也就是昨天有股票，今天运气好，价格高，我刚刚卖了股票这一种可能。 # dp[i][1] = dp[i-1][0] + prices[i] # dp[i][2]表示第i天结束之后，我没有股票，但是明天不在冷冻期，也就是今天我不买股票，有可能因为我昨天刚刚卖了，今天就是冷冻期，我买不了。也有可能，昨天的我可能没打算买，今天又不买。 # dp[i][2] = max(dp[i-1][1] ,dp[i-1][2]) if not prices: return 0 n = len(prices) # 第0天dp[0][0]要买是第一个股 dp = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)] for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] = dp[i-1][0] + prices[i] dp[i][2] = max(dp[i-1][1] ,dp[i-1][2]) return max(dp[-1][1], dp[-1][2])


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

买卖股票的最佳时机（买N次加手续费）

这是Leetcode的第714题： 买卖股票的最佳时机（买N次加手续费）

注释写得很详细了。

# 就是在dp[i][0]减去手续费而已
class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) if n == 0: return 0 dp = [[0]*2 for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1,n): dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]-fee) dp[i][1] = max(dp[i-1][0]-prices[i] ,dp[i-1][1]) return dp[-1][0]


class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: # cash表示第i天结束，没有股票的最大利润 # hold表示第i天结束，有股票的最大利润 cash, hold = 0, -prices[0] for i in range(1,len(prices)): cash = max(cash,hold+prices[i]-fee) hold = max(hold,.cash-prices[i]) return cash

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

后言（杂聊）

上面就是今天的股票系列刷题，今天也就刷了dp的Leetcode题。

现在爱上生活，爱上每天的细节，爱上写日常，尝试给自己降压，写鼓励的话语。

九月，不敢浪，也浪不起。我决定每天在每篇博客中添加keep打卡。

生活这趟旅途，你我都是行人，不会有人永远与其他人都是背道而驰。至于活着的意义，本就没什么标准答案，真的开心就好，当你感到无聊那就改变，当你感到厌倦那就停一停。”

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/108812172