合縱連橫: 從DP框架理解 最佳股票買賣系列題 的背後本質

小松鼠-avatar-img
發佈於演算法題目解析 個房間
更新於 發佈於 閱讀時間約 21 分鐘

這篇文章,會帶著大家複習以前學過的FSM+DP框架
並且以有限狀態機 + DP狀態轉移的概念為核心,

貫穿一些相關聯最佳股票買賣系列的題目,
透過框架複現來幫助讀者理解這個實用的演算法框架。


基本的FSM + DP 框架,配合交易邏輯。


針對每一天,其實歸根究柢只有兩種狀態

第一種手上都持有現金。

第二種手上持有股票


每天進行的動作,也只有兩種可能情況:
假如今天結束的時候,是都持有現金
代表昨天就已經持有現金今天繼續持有;或者,昨天持有股票,今天選擇賣出股票

假如今天結束的時候,是持有股票
代表昨天就已經持有股票今天繼續抱著;或者,昨天持有現金,今天選擇買入股票


寫成虛擬碼或者演算法的話,可以這樣表達

DP[day_d, KeepCash] 
= max( DP[day_d-1, KeepCash], DP[day_d-1, HoldStack] + stockPrice[day_d] )

DP[day_d, HoldStock]
= max( DP[day_d-1, HoldStock], DP[day_d-1, KeepCash] - stockPrice[day_d] )


接下來,我們會用這個上面這種結構,貫穿一些同類型,有關聯的題目
(請讀者、或觀眾留意上面的這種 FSM+ DP 動態規劃 框架,之後的解說會反覆出現)


FSM有限狀態機 + DP 動態規劃框架 示意圖

raw-image

打鐵趁熱,現在來看最佳股票買賣系列題第一題。

Best time to buy and sell stock


這題的限制條件是只能做一組交易(也就是一次買入,一次賣出)。

只有一次買入,相當於會從某一天選擇買入,之後就只能選另一天賣出了。

某一天買入之前一定是沒賺沒賠,所以寫成式子就是 0 - stock_price


最後用FSM+DP框架的思考邏輯寫成程式碼,就是下方這個樣子

    
class Solution:
def maxProfit(self, prices: List[int]) -> int:

# It is impossible to have stock to sell on first day, so -infinity is set as initial value
cur_hold, cur_cash = -float('inf'), 0


for stock_price in prices:

prev_hold, prev_cash = cur_hold, cur_cash

# either keep in hold, or just buy today with stock price
cur_hold = max(prev_hold, 0-stock_price)

# either keep in cash, or just sell today with stock price
cur_cash = max(prev_cash, prev_hold + stock_price)


# max profit must be in Cash state
return cur_cash

接著來看變化題,最佳股票買賣系列題第二題。

Best time to buy and sell stock II

這題比較寬鬆,不限制交易組數,也就是可以交易任意多組
買入股票n次,賣出股票n次。

也就是說,某一天才買入的狀態會相依於前一天現金部位的狀態

所以寫成式子就是 dp[day-1, KEEP_CASH] - stock_price


最後用FSM+DP框架的思考邏輯寫成程式碼,就是下方這個樣子

class Solution:
def maxProfit(self, prices: List[int]) -> int:

# Use constant literal to help reader understand source code below.
HOLD_STOCK, KEEP_CASH = 0, 1

## Dictionary (Hash table)
# key: (day, state) pair
# value: coreesponding maximal profit
dp = {}

# No free lunch, it is impoosible to have stock before first trading day
dp[-1, HOLD_STOCK] = -math.inf

# No gain, no loss before first trading day
dp[-1, KEEP_CASH] = 0

# For each day with corresponding stock price in stock market
for day, stock_price in enumerate(prices):

# If today we have stock, either we already had it yesterday, or we just buy stock and hold it today.
dp[day, HOLD_STOCK] = max( dp[day-1, HOLD_STOCK], dp[day-1, KEEP_CASH] - stock_price)

# If today we keep cash, either we already kept cash yesterday, or we just sell out stock today
dp[day, KEEP_CASH] = max( dp[day-1, KEEP_CASH], dp[day-1, HOLD_STOCK] + stock_price)

#---------------------------------------------------------------
# To get maximal realized profit, final state must be KEEP_CASH.
last_day = len(prices)-1
return dp[last_day, KEEP_CASH]

Best time to buy and sell stock II 空間優化的程式碼實作

仔細觀察,可以發現每天的狀態只依賴前一天的狀態去更新

因此,可以用之前學過的狀態壓縮的技巧,把表格拿掉,
改成只用變數儲存狀態,節省空間,從O(n)空間降到O(1)常數級別。

class Solution:
def maxProfit(self, prices: List[int]) -> int:

# It is impossible to sell stock on first day, set -infinity as initial value for cur_hold
cur_hold, cur_cash = -float('inf'), 0

for stock_price in prices:

prev_hold, prev_cash = cur_hold, cur_cash

# either keep hold, or buy in stock today at stock price
cur_hold = max( prev_hold, prev_cash - stock_price )

# either keep cash, or sell out stock today at stock price
cur_cash = max( prev_cash, prev_hold + stock_price )

# maximum profit must be in Cash state
return cur_cash

有了狀態圖以後,再回來看程式碼清晰許多了,對吧!

接下來,為了再更逼真一點延伸題就是把交易的額外成本fee(稅, 手續費)也加入考量

延伸題就是

Best time to buy and sell stock with transaction fee

那也很容易,我們就在每組交易進行的時候,額外多扣一個費用fee即可。


註: 不失一般性,我們選擇在買入股票時付出額外的交易成本費用fee
讀者想要在賣出時扣掉也可以,可以試著改改看,也能通過測試


Best time to buy and sell stock with transaction fee 程式碼實作

class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:

cur_hold, cur_cash = -math.inf, 0

for stock_price in prices:

prev_hold, prev_cash = cur_hold, cur_cash

# either keep cash, or sell out today at stock price
cur_cash = max(prev_cash, prev_hold + stock_price )

# either keep hold, or buy in today at stock price and pay transaction fee for this trade
cur_hold = max(prev_hold, prev_cash - stock_price - fee)

# maximum profit must be in not-hold state
return cur_cash

好,接著來看進階題,最佳股票買賣系列題第三題。

Best time to buy and sell stock III

這題的限制條件是最多只能兩組交易(也就是各兩次買入,各兩次賣出)。

也就是說,第i次的買入並且持有股票的狀態,
前面會相依於第(i-1)次賣出並且持有現金的狀態。

所以寫成式子就是 dp[KEEP_CASH, i-1] - stock_price


最後用FSM+DP框架的思考邏輯寫成程式碼,就是下方這個樣子

class Solution:
def maxProfit(self, prices: List[int]) -> int:

HOLD_STOCK, KEEP_CASH = 0, 1

# dictionary
# key: state, kth-transaction
# value: corresponding profit
dp = defaultdict(int)

# No free lunch, impoosible to have stock before first trading day
dp[(HOLD_STOCK, 0)] = -math.inf
dp[(HOLD_STOCK, 1)] = -math.inf
dp[(HOLD_STOCK, 2)] = -math.inf


for stock_price in prices:

## For 1st transaction:
# Either we kept cash already, or we just sell out stock today
dp[KEEP_CASH, 1] = max(dp[KEEP_CASH, 1], dp[HOLD_STOCK, 1] + stock_price )

# Either we had stock already, or we just buy in stock today ( add one more transaction)
dp[HOLD_STOCK, 1] = max(dp[HOLD_STOCK, 1], dp[KEEP_CASH, 0] - stock_price)

## For 2nd transaction:
# Either we kept cash already, or we just sell out stock today
dp[KEEP_CASH, 2] = max(dp[KEEP_CASH, 2], dp[ HOLD_STOCK, 2] + stock_price)

# Either we had stock already, or we just buy in stock today ( add one more transaction)
dp[HOLD_STOCK, 2] = max(dp[HOLD_STOCK, 2], dp[KEEP_CASH, 1] - stock_price)

# Maximal profit must be KEEP_CASH on last day
# (This means we cash out and sell stocks finally)
return dp[KEEP_CASH, 2]


仔細觀察,其實for loop裡面包含著一個階梯迭代更新的關係。

第i組的交易狀態更新,只依賴第i組和第i-1組的狀態。

抽象化+結構化,可以寫成這個形式

for trans in range(1, k+1):

dp[HOLD_STOCK, trans] = max( dp[HOLD_STOCK, trans], dp[KEEP_CASH, trans-1 ] - stock_price )

dp[KEEP_CASH, trans] = max( dp[KEEP_CASH, trans], dp[HOLD_STOCK, trans] + stock_price )

寫成這個形式,也相當於推廣成

最多只能k組交易下的最佳股票買賣模式

當我們推導出這個通則的時候,其實無形中已經把下一題也解出來了! XD


下一題就是

Best time to buy and sell stock IV

這題的限制條件是最多只能k組交易(也就是各k次買入,各k次賣出)。

這邊承接第剛剛上面推導出來的通則,順著寫下來即可。

class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:

n = len(prices)

HOLD_STOCK, KEEP_CASH = 0, 1

dp = defaultdict(int)
for k in range (0, k+1):
dp[HOLD_STOCK, k] = -math.inf

for stock_price in prices:

for trans in range(1, k+1):
dp[HOLD_STOCK, trans] = max( dp[HOLD_STOCK, trans], dp[KEEP_CASH, trans-1 ] - stock_price )

dp[KEEP_CASH, trans] = max( dp[KEEP_CASH, trans], dp[HOLD_STOCK, trans] + stock_price )

return dp[KEEP_CASH, k]

萬變不離其宗,其實DP狀態轉移的觀念其實都是相通的。


最後一題是一個延伸變化題

Best Time to Buy and Sell Stock with Cooldown

這題的也是不限制交易組數,也就是可以交易任意多組

買入股票n次,賣出股票n次。

也就是說,某一天才買入的狀態會相依於前一天現金部位的狀態


但是,多了一個冷卻條件,
股票賣出之後,會強迫進入冷卻日一天,冷卻日的次日才可以再買入股票


畫成FSM有限狀態機的狀態圖就是

raw-image

順著狀態圖的更新邏輯寫下迭代耕新的程式碼即可

class Solution:
def maxProfit(self, prices: List[int]) -> int:

# initialization
cool_down, sell, hold = 0, 0, -float('inf')

for stock_price_of_Day_i in prices:

prev_cool_down, prev_sell, prev_hold = cool_down, sell, hold

# Max profit of cooldown on Day i comes from either cool down of Day_i-1, or sell out of Day_i-1 and today Day_i is cooling day
cool_down = max(prev_cool_down, prev_sell)

# Max profit of sell on Day_i comes from hold of Day_i-1 and sell on Day_i
sell = prev_hold + stock_price_of_Day_i

# Max profit of hold on Day_i comes from either hold of Day_i-1, or cool down on Day_i-1 and buy on Day_i
hold = max(prev_hold, prev_cool_down - stock_price_of_Day_i)


# The action of final trading day must be either sell or cool down
return max(sell, cool_down)

可以視為Best time to buy and sell stock II的延伸題(多了額外的冷卻條件)


結語

好,今天一口氣介紹了最精華的部分,

通用的FSM有限狀態機 + DP狀態轉移框架,還有相關的衍伸變化題與演算法建造流程。


希望能幫助讀者、觀眾徹底理解它的原理,

並且能夠舉一反三,洞察其背後的本質和了解相關的應用領域!


感謝收看囉! 我們下篇文章再見~

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/06/08
DP演算法框架 與 推薦的DP學習路徑 (持續更新中)提及了這篇文章,趕快過去看看吧!
小松鼠-avatar-img
發文者
2024/06/01
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
看更多
你可能也想看
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
上週的 1/26 EURUSD 走得很漂亮, 是個很優秀的 AMD 模範生👍🏻 不過也脫離不了上一篇內容有提到的概念, 就是 「平衡 Balance」 我一樣會以這個視角來討論,然後進階一點點 🤏🏻 一樣也是邏輯、概念為主, 不是分享我怎麼常在極端價格進場交易的策略
Thumbnail
上週的 1/26 EURUSD 走得很漂亮, 是個很優秀的 AMD 模範生👍🏻 不過也脫離不了上一篇內容有提到的概念, 就是 「平衡 Balance」 我一樣會以這個視角來討論,然後進階一點點 🤏🏻 一樣也是邏輯、概念為主, 不是分享我怎麼常在極端價格進場交易的策略
Thumbnail
本篇文章分享了在近期市場波動中的交易經驗與學習,強調退場機制、槓桿比例和靈活性的重要性,以及應對市場風險的計畫。作者透過個人經歷,討論如何在多頭和回檔期小心操作並尋找最佳進場時機,同時也從市場行為的觀察中提出對策略建立的見解,認為應該在上漲時就開始規劃,而非遇到困難時才想出對策。
Thumbnail
本篇文章分享了在近期市場波動中的交易經驗與學習,強調退場機制、槓桿比例和靈活性的重要性,以及應對市場風險的計畫。作者透過個人經歷,討論如何在多頭和回檔期小心操作並尋找最佳進場時機,同時也從市場行為的觀察中提出對策略建立的見解,認為應該在上漲時就開始規劃,而非遇到困難時才想出對策。
Thumbnail
本策略採用5、30分K的支撐與壓力進行突破買進與跌破賣出策略,透過盤中的量能變化進行買賣操作策略,該指標能夠真實地反映出價格的波動情況,並且可以靈活地調整參數進行進出場操作。 此策略主要是針對看盤的經驗,將策略轉化為程式進行自動化交易,減少人為的操作
Thumbnail
本策略採用5、30分K的支撐與壓力進行突破買進與跌破賣出策略,透過盤中的量能變化進行買賣操作策略,該指標能夠真實地反映出價格的波動情況,並且可以靈活地調整參數進行進出場操作。 此策略主要是針對看盤的經驗,將策略轉化為程式進行自動化交易,減少人為的操作
Thumbnail
這篇文章主要介紹瞭如何使用一眼辨多空線和Superbollinger Trend來判斷個股的多空情況以及強弱循環。同時也提到了一些多方股和空方股的例子,以及即將舉行的用戶活動預告。文章內容涉及股市操作邏輯和注意事項。
Thumbnail
這篇文章主要介紹瞭如何使用一眼辨多空線和Superbollinger Trend來判斷個股的多空情況以及強弱循環。同時也提到了一些多方股和空方股的例子,以及即將舉行的用戶活動預告。文章內容涉及股市操作邏輯和注意事項。
Thumbnail
前幾個篇章已大致講完技術分析的原理,本篇是前篇的延伸,當我們觀察趨勢中的壓力與支撐時,如果出現特定結構的型態,此時是技術線型發出的強烈訊號,必須好好重視。有哪三種型態是.......
Thumbnail
前幾個篇章已大致講完技術分析的原理,本篇是前篇的延伸,當我們觀察趨勢中的壓力與支撐時,如果出現特定結構的型態,此時是技術線型發出的強烈訊號,必須好好重視。有哪三種型態是.......
Thumbnail
用多空趨勢線串聯股市金脈簡單來說內建一套投資邏輯,這套系統基於經濟學中的「適應性預期理論」發展而來,主要依賴過去的觀察和經驗來進行投資。這本書橫跨了產業面、基本面、技術面與籌碼面,我覺得下面的重點,你可以思考一下對你的投資有沒有幫助。
Thumbnail
用多空趨勢線串聯股市金脈簡單來說內建一套投資邏輯,這套系統基於經濟學中的「適應性預期理論」發展而來,主要依賴過去的觀察和經驗來進行投資。這本書橫跨了產業面、基本面、技術面與籌碼面,我覺得下面的重點,你可以思考一下對你的投資有沒有幫助。
Thumbnail
接下來的講座將帶給同學們一個全新的策略設計觀點,一般選擇權教學絕對教不來的知識,這也是有驚無險流的策略之所以比別家的策略有效的重要原因。 篇幅較長,所以會拆成兩篇。
Thumbnail
接下來的講座將帶給同學們一個全新的策略設計觀點,一般選擇權教學絕對教不來的知識,這也是有驚無險流的策略之所以比別家的策略有效的重要原因。 篇幅較長,所以會拆成兩篇。
Thumbnail
這篇文章談論股匯市的關係和適性趨勢軌道的寬窄意義,以及超級趨勢布林趨勢指標的設定和彩虹ATI+日ATI複習。觀看影片可以幫助吸收裡面的邏輯。
Thumbnail
這篇文章談論股匯市的關係和適性趨勢軌道的寬窄意義,以及超級趨勢布林趨勢指標的設定和彩虹ATI+日ATI複習。觀看影片可以幫助吸收裡面的邏輯。
Thumbnail
這篇文章,會帶著大家複習以前學過的FSM+DP框架, 並且以有限狀態機 + DP狀態轉移的概念為核心, 貫穿一些相關聯最佳股票買賣系列的題目, 透過框架複現來幫助讀者理解這個實用的演算法框架。 基本的FSM + DP 框架,配合交易邏輯。 針對每一天,其實歸根究柢只有兩種狀態。 第一種
Thumbnail
這篇文章,會帶著大家複習以前學過的FSM+DP框架, 並且以有限狀態機 + DP狀態轉移的概念為核心, 貫穿一些相關聯最佳股票買賣系列的題目, 透過框架複現來幫助讀者理解這個實用的演算法框架。 基本的FSM + DP 框架,配合交易邏輯。 針對每一天,其實歸根究柢只有兩種狀態。 第一種
Thumbnail
一般常見的時間架構分成三個:趨勢級別、分析級別、進場級別。 趨勢級別 週線 or 日線,目的是為了確認整體市場的方向,以及關鍵流動性區域(支撐、壓力位) 分析級別 4H or 1H,目的是確認市場當前方向、公允價值缺口、訂單塊、流動性區域、高期望值交易區域,需要花較多時間來分析。 進場級別
Thumbnail
一般常見的時間架構分成三個:趨勢級別、分析級別、進場級別。 趨勢級別 週線 or 日線,目的是為了確認整體市場的方向,以及關鍵流動性區域(支撐、壓力位) 分析級別 4H or 1H,目的是確認市場當前方向、公允價值缺口、訂單塊、流動性區域、高期望值交易區域,需要花較多時間來分析。 進場級別
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News