@Author：Runsen

@Date：2020/09/26

悄然間時間來到十月，不禁感慨，過去的這一個月浪的‘無知’，我其實是一個很沒有原則的人，做的很多事情都是隨心所欲，骨子里放縱不羈愛自由。可能是最后一年的時間了吧，自己在學業上沒有了太多心勁，抱著一種‘再不瘋狂就老了’的心態開始游戲人生，放縱自我，或許沒有那么嚴重，但確實實實在在的放飛自我了。

還有一個關鍵原因是每次想到自己專業都會一陣心痛，宿舍成天游戲，我還要為補考和知行分焦慮，這世間我仿佛覺得大一自己入IT的門，但又不是自己的專業，都是憑自己一天一天積累而來。畢業卻為畢業證而焦慮的恐慌，學分績點1.47，專業排名倒數第七，我哪里差了？都不知道我大學這么努力，還要給人看死。

不說了。趕緊開干Leetcode的股票系列。前面都是發牢騷！自己不滿足自己的現狀而已！

在極客時間中，我知道動態規劃必須要面對股票系列，背包系列差不多了，那就上吧。

文章目錄

• 買賣股票的最佳時機（買一次）
• 買賣股票的最佳時機（買N次）
• 買賣股票的最佳時機（買2次）
• 買賣股票的最佳時機（買k次）
• 買賣股票的最佳時機（買N次加CD冷卻時間）
• 買賣股票的最佳時機（買N次加手續費）
• 后言（雜聊）

買賣股票的最佳時機（買一次）

這是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 0dp = [0] * nminprice = 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]

買賣股票的最佳時機（買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 0dp = [[0]*2 for _ in range(n)]dp[0][0] = 0dp[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 = 0if n == 0 : return 0for 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

買賣股票的最佳時機（買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 0n = 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]

買賣股票的最佳時機（買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 0n = len(prices)res = []# 如果k的次數大于n//2，那么就是直接計算利潤，第一天買，第二天就賣，然后第二天在買。if k > n // 2: max_profit = 0for i in range(1,n):profit = prices[i] - prices[i - 1]# 如果第二天比第一天高，那就直接加入if profit > 0:max_profit += profitreturn 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)

買賣股票的最佳時機（買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 0n = 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])

買賣股票的最佳時機（買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 0dp = [[0]*2 for _ in range(n)]dp[0][0] = 0dp[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

后言（雜聊）

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

現在愛上生活，愛上每天的細節，愛上寫日常，嘗試給自己降壓，寫鼓勵的話語。

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

生活這趟旅途，你我都是行人，不會有人永遠與其他人都是背道而馳。至于活著的意義，本就沒什么標準答案，真的開心就好，當你感到無聊那就改變，當你感到厭倦那就停一停。”

總結

以上是生活随笔為你收集整理的股票系列，动态规划，加油，九月太浪了，十月不许浪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。