資訊專欄INFORMATION COLUMN
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導圖源文件問題請點擊此鏈接.
想進大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法, 博主同步更新了算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
關注博主獲得題解更新的最新消息!!!
本題最難的地方就在于 dp數組的構建了, 因為它不像前面講過的兩道股票問題那樣, dp數組只需要用兩種狀態就可以表示了: 當天持有/不持有股票. 本題由于加了 最多買賣兩次 的條件, 使問題一下子就變得復雜了, 用之前的兩種狀態并不能體現 最多買賣兩次 的限制, 所以我們需要重新設計dp數組.
用上圖中的五種狀態就可以完美地體現出 最多買賣兩次 的限制, 然后經過分析可以看出第一種狀態利潤為0, 對結果沒什么影響, 所以我們最終只要定義剩下的4個狀態即可. 定義dp數組的名稱還是一貫地采用比較容易識別的名稱, 這比那些用到二維dp數組, 甚至有些題解用到了三維dp數組要好多了.
定義出了dp數組之后, 按照前面兩題的經驗, 遞推公式就沒太大難度了, 還是每種狀態都由兩種情況組合而來, 最終取最大值:
本題的初始化也有一定難度, 畢竟dp數組實在太多了.
先來明確下題目中的隱含條件: 無論題目中是否允許「在同一天買入并且賣出」這一操作, 最終的答案都不會受到影響, 這是因為這一操作帶來的收益為零, 所以為了方便初始化, 這里默認是可以的. 于是就有了下面的初始化過程:
如果題目不允許的話, 那初始化就會稍微麻煩一些了, 比如sell1[i]就只能在第二天進行sell1[1]的初始化了, 同理: buy2[i]在第三天進行buy2[2]的初始化, sell2[i]在第四天進行sell2[3]的初始化, 這就是能否「在同一天買入并且賣出」的不同之處.
在動態規劃結束后,由于我們可以進行不超過兩筆交易,因此最終的答案在0,sell1[i],sell2[i]中, 且為三者中的最大值, 由于在邊界條件中sell1[i],sell2[i]的值已經為0, 并且在狀態轉移的過程中我們維護的是最大值, 因此sell1[i],sell2[i]最終一定大于等于0.
同時, 如果最優的情況對應的是恰好一筆交易, 那么它也會因為我們在轉移時允許在同一天買入并且賣出這一寬松的條件, 從sell1[i]轉移至sell2[i], 可以理解假如最優是 sell1[i] 的話, 可以當天再做一次買賣, 也就是完成兩次交易, 所以無論如何都可以是 sell2[i] 最優.
代碼在空間優化上和我們之前說過的直接將數組用變量來替換就可以了, 但是它在理解上還是有一定難度的.
例如在計算sell1[i]時, 我們直接使用buy1[i]而不是buy1[i-1]進行轉移。buy1[i]比 buy[i-1]多考慮的是在第i天買入股票的情況, 而轉移到sell1[i]時, 考慮的是在第i天賣出股票的情況, 這樣在同一天買入并且賣出收益為零, 不會對答案產生影響, 所以我們才能這樣進行優化.
## 未進行空間優化class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) buy1 = [0] * n sell1 = [0] * n buy2 = [0] * n sell2 = [0] * n buy1[0] = buy2[0] = -prices[0] sell1[0] = sell2[0] = 0 for i in range(1, n): buy1[i] = max(buy1[i-1], -prices[i]) sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i]) buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i]) sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i]) return sell2[-1]## 空間優化class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) buy1 = buy2 = -prices[0] sell1 = sell2 = 0 for i in range(1, n): buy1 = max(buy1, -prices[i]) sell1 = max(sell1, buy1 + prices[i]) buy2 = max(buy2, sell1 - prices[i]) sell2 = max(sell2, buy2 + prices[i]) return sell2//未進行空間優化class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] buy1 = new int[n]; int[] sell1 = new int[n]; int[] buy2 = new int[n]; int[] sell2 = new int[n]; buy1[0] = -prices[0]; sell1[0] = 0; buy2[0] = -prices[0]; sell2[0] = 0; for (int i = 1; i < n; ++i) { buy1[i] = Math.max(buy1[i-1], -prices[i]); sell1[i] = Math.max(sell1[i-1], buy1[i-1] + prices[i]); buy2[i] = Math.max(buy2[i-1], sell1[i-1] - prices[i]); sell2[i] = Math.max(sell2[i-1], buy2[i-1] + prices[i]); } return sell2[n-1]; }}我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟件/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/數據結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟件工程初試906科目
最值得收藏的 計算機網絡 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 數據結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字圖像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和刪除問題 包含詳細操作原理 情況對比
各種常見排序算法的時間/空間復雜度 是否穩定 算法選取的情況 改進 思維導圖整理
人工智能課件 算法分析課件 Python課件 數值分析課件 機器學習課件 圖像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟件學院軟件工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟件工程 906 數據結構 C++ 歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
科技相關 小米手機
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/122206.html
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
閱讀 2866·2021-11-11 10:58
閱讀 1920·2021-10-11 10:59
閱讀 3488·2019-08-29 16:23
閱讀 2324·2019-08-29 11:11
閱讀 2784·2019-08-28 17:59
閱讀 3838·2019-08-27 10:56
閱讀 2049·2019-08-23 18:37
閱讀 3111·2019-08-23 16:53
