此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
關注博主獲得題解更新的最新訊息!!!
文章目錄
- 0.導圖整理
- 1.dp陣列的構建
- 2.確定遞推公式
- 3.dp陣列初始化
- 4.最侄訓傳結果
- 5.幾個重要的注意點
- 5.1 k的正序和倒序
- 5.2 k的范圍
- 5.3 have陣列的維數
- 5.4 Integer.MIN_VALUE / 2
- 5.5 j的回圈
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/si-wei-dao-tu-zheng-li-dpshu-zu-gou-jian-e97c/
0.導圖整理
1.dp陣列的構建
本題在形式上似乎是 股票III最多買賣兩次 的進階版, 但其實本題是所有股票問題的通解問題, 其他的股票問題只是在k的取值上有所不同, 但它們的思想都可以用本題的思想來解決, 之后也會單獨寫一篇文章來總結所有的股票問題.
對于dp陣列的定義, 我們首先要確定一共有多少個狀態, 通過前面幾道題目的訓練, 我們可以確定的狀態有: 當天的天數i, 當天是否持有股票. 但本題的特殊之處在于: 我們必須還要確定當前進行了幾筆交易j, 因為前面的幾道題中, k要么是1, 要么是正無窮, 所以我們也不需要將它單獨作為一個狀態, 但本題就不同了, k可以取任意的值, 所以它也必須作為一個狀態.
所以本題必須用3個狀態才能完整表示dp陣列, 也就是三維dp陣列, 按照我們之前說過的方法, 可以通過命名來優化一個狀態, 也就是have表示持有狀態, no表示不持有狀態(我覺得這樣的命名比官方的buy, sell更明確), 所以最終的dp陣列就是二維dp陣列:
- have[i][j]表示進行恰好 j 筆交易, 并且當前手上持有一支股票, 這種情況下的最大利潤.
- no[i][j] 表示進行恰好 j 筆交易, 并且當前手上不持有股票, 這種情況下的最大利潤.
這里我們必須還要明確一個概念: k何時進行變化. 這點很重要, 直接就導致之后遞推公式的不同. 官方題解是默認一買一賣才算完整交易一次, 買入不算交易, 賣出才算一次交易, 所以只有賣出時k變化. 當然也有人定義的是買入時k變化, 這種就會產生不同的遞推公式, 但都是正確的.
2.確定遞推公式
定義出了dp陣列之后, 按照前面幾題的經驗, 遞推公式就沒太大難度了, 還是每種狀態都由兩種情況組合而來, 最終取最大值:
根據上面我們定義的k何時變化, 體現在遞推公式中就是在推導no[i][j]的第二種情況時用到的have[i-1][j-1], 因為賣出股票時k會變化, 所以上一個持有股票的狀態就是k-1了. 這點一定要注意, 它不止在遞推公式中很重要, 也在之后的空間優化時很重要!
3.dp陣列初始化
本題的初始化程序還是有點復雜的, 但是并不難理解, 這里就不多解釋了:
4.最侄訓傳結果
由于在所有的 n 天結束后, 手上不持有股票對應的最大利潤一定是嚴格大于手上持有股票對應的最大利潤的, 然而完成的交易數并不是越多越好（例如陣列prices 單調遞減,我們不進行任何交易才是最優的）, 因此最終的答案即為no[n?1][0…k]中的最大值.
5.幾個重要的注意點
5.1 k的正序和倒序
本題為了避免狀態壓縮造成的資料覆寫, 應該采用k倒序才對. 它的解釋如下: 最后一行計算no[j](no[i][j])時所用的have[j-1], 本應為have[i-1][j-1]，然而由于采用了狀態壓縮, i不變, j的前一個回圈剛剛計算了have[i][j-1]賦值給了have[j-1], 所以have[j-1]實際為have[i][j-1], 與轉移方程產生了偏差.
這是需要采用倒序的原因, 但是本題采用正序也是可以得到相同的結果的, 官方對此也進行了解釋, 當然也有人專門寫了文章進行推理說明, 導圖中也放了相應的鏈接, 感興趣的可以去看看, 程序還是挺復雜的.
但是從實際來說, 將k進行倒序, 在代碼上是非常容易實作的操作, 只有在j的遍歷范圍上有一點改動, 其他是完全一樣的, 所以我們還是盡可能用倒序遍歷保證安全性, 畢竟本題沒有影響, 不代表其他動態規劃的題目也沒有影響, 而且這么容易實作的操作, 根本沒什么成本代價可言!
5.2 k的范圍
如果交易次數大于n/2, 必然存在有一天交易了兩次, 然而這是毫無意義的, 因為 n 天最多只能進行?n/2? 筆交易, 其中?x? 表示對x向下取整，因此我們可以將 k 對?n/2? 取較小值之后再進行動態規劃.
5.3 have陣列的維數
k+1維是沒問題的, 如果維數只有k, 就表示不了交易0次了, 要是陣列一直是遞減的, 一交易就是虧損.
5.4 Integer.MIN_VALUE / 2
在這是在java中可能遇到的問題, 因為在之后的操作中可能會減去prices[i], 這樣就可能導致Integer.MIN_VALUE越界翻轉, 所以這里進行了除以2的操作, 在python中是不用擔心這個問題的.
5.5 j的回圈
no[i][j]的狀態轉移方程中包含have[i?1][j?1], 在j=0 時其表示不合法的狀態, 因此在 j=0 時, 我們無需對 no[i][j] 進行轉移, 讓其保持值為 0 即可, 所以在j=0時, 我們需要單獨對have[i][0]進行處理.
原始碼
Python:
## 未進行空間優化
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
k = min(k, n // 2) # k最大為總天數的一半
have = [[0] * (k + 1) for _ in range(n)]
no = [[0] * (k + 1) for _ in range(n)]
have[0][0], no[0][0] = -prices[0], 0
for i in range(1, k + 1): # 不合法狀態
have[0][i] = no[0][i] = float("-inf")
for i in range(1, n): # j=0時, no[i][0]不合法
have[i][0] = max(have[i - 1][0], no[i - 1][0] - prices[i])
for j in range(1, k + 1):
have[i][j] = max(have[i - 1][j], no[i - 1][j] - prices[i])
no[i][j] = max(no[i - 1][j], have[i - 1][j - 1] + prices[i]);
return max(no[n - 1])
## 進行空間優化
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
k = min(k, n // 2) # k最大為總天數的一半
have = [0] * (k + 1)
no = [0] * (k + 1)
have[0], no[0] = -prices[0], 0
for i in range(1, k + 1): # 不合法狀態
have[i] = no[i] = float("-inf")
for i in range(1, n): # j=0時, no[0]不合法
have[0] = max(have[0], no[0] - prices[i])
for j in range(k, 0, -1): # 優化空間, k倒序
have[j] = max(have[j], no[j] - prices[i])
no[j] = max(no[j], have[j - 1] + prices[i]);
return max(no)
java:
// 未進行空間優化
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2); // k最大為總天數的一半
int[][] have = new int[n][k + 1];
int[][] no = new int[n][k + 1];
have[0][0] = -prices[0];
no[0][0] = 0;
for (int i = 1; i <= k; ++i) { // 不合法狀態,/2防止越界翻轉
have[0][i] = no[0][i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) { // j=0時, no[i][0]不合法
have[i][0] = Math.max(have[i - 1][0], no[i - 1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
have[i][j] = Math.max(have[i - 1][j], no[i - 1][j] - prices[i]);
no[i][j] = Math.max(no[i - 1][j], have[i - 1][j - 1] + prices[i]);
}
}
return Arrays.stream(no[n - 1]).max().getAsInt();
}
}
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比
各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理
人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理
東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 歷代手機型號大全 發布時間 發布價格
常見手機品牌的各種系列劃分及其特點
歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/317990.html
標籤：其他