此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
關注博主獲得題解更新的最新訊息!!!
文章目錄
- 0.導圖整理
- 1.兩個狀態的動態規劃
- 1.1 兩個狀態的思想
- 1.2 遞推公式的變化
- 1.3 no[i-2]是否為最大利潤
- 1.4 初始化的不同
- 1.5 空間優化的難點
- 2.三個狀態的動態規劃
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/si-wei-dao-tu-zheng-li-liang-chong-dpshu-4vu3/
0.導圖整理
1.兩個狀態的動態規劃
1.1 兩個狀態的思想
本題就是在 股票II買賣多次 的基礎上增加了冷凍期的條件, dp陣列定義程序基本相似, 大家可以先看完上面的題解, 再來看本題題解.
大家在看其他題解的時候, 肯定大部分都是三個狀態的動態規劃解法, 這種解法也確實符合一般的思路, 畢竟前面幾題我們大多都定義的兩個狀態: 持有have[i]和不持有no[i]股票, 現在多了個冷凍期的附加條件, 那自然想到再多加一個狀態單獨表示冷凍期的情況. 但總感覺這樣的三個狀態和前面幾題就不統一了, 那么能不能還用兩個狀態解決此題呢?
我們首先觀察下冷凍期的概念, 它是在股票賣出之后才會出現的情況, 也就是說處于冷凍期時一定是不持有股票的, 所以可以將它合并到狀態no[i]中, 這樣就將三個狀態成功轉化為兩個狀態了.
1.2 遞推公式的變化
狀態定義完了, 就是遞推公式的推導了, 根據之前的經驗, 遞推公式由四種情況組合而成, 而這四種情況中和冷凍期有關的就只有 第i天買入股票 的情況了, 其他的三種狀態都和冷凍期關系不大, 并未受太大影響, 遞推公式也沒什么變化.
下面我們就來著重分析這種情況, 當第i天買入股票時, 那第i-1天必定是不持有股票且不能是冷凍期, 而只用no[i-1]這個狀態并不能區別出是否為冷凍期, 所以這里我們采用no[i-2]這個狀態.
現在我們來說明這個狀態的合理性: no[i-2]由兩種情況組成:
- 如果no[i-2]是在第i-2天賣出股票, 那第i-1天就是冷凍期, 那第i天就解凍了.
- 如果no[i-2]是延續了前一天i-3天不持有股票的狀態, 那么在第i-1天就不會有股票被賣出, 那么第i天也不會是冷凍期.
綜合上述兩種情況, 無論no[i-2]是由哪個情況轉移而來, 第i天都不是冷凍期.
1.3 no[i-2]是否為最大利潤
上述說明了使用了no[i-2]的合理性, 那么就剩最后一個問題了, 我們跳過了no[i-1]這個狀態, 那么no[i-2]是否就是當前的最大利潤呢?
這里還是用上述no[i-2]的兩種情況來說明:
- 如果no[i-2]是在第i-2天賣出股票, 那第i-1天就是冷凍期, 利潤不會發生變化.
- 如果no[i-2]是延續了前一天i-3天不持有股票的狀態, 那么在i-1天可能延續i-2天不持有股票的狀態, 利潤仍然不變, 也可能在i-1天買入股票, 首先利潤就變小了, 其次狀態也變為have[i-1], 不是我們需要的no狀態.
綜合兩種情況來看, no[i-2]就是當前的最大利潤, 這點理解之后, 遞推公式就沒什么難度了.
1.4 初始化的不同
之前都是初始化了have[0]和no[0]兩個狀態就可以了, 本題由于使用到了no[i-2]這個狀態, 在i=1時是不合法的, 所以本題還要初始化have[1]和no[1]兩個狀態, 根據遞推公式就可以了, 也沒什么難度, 就是麻煩了一點.
1.5 空間優化的難點
本題在空間優化上是有點難度的, 因為我們需要用到no[i-2]的狀態, 所以必須用變數同時存盤no[i-2]和no[i-1]的狀態, 變數記錄的位置要確定好, 具體實作可以看最后的代碼.
2.三個狀態的動態規劃
上文提到了最常規的思想就是在兩個狀態的基礎上再新增一個狀態用來表示冷凍期, 當然no[i]的含義也發生了一點的變化
- have[i] 表示第i天持有股票所得最多現金
- no[i] 表示第i天不持有股票且不處于冷凍期所得最多現金
- cold[i] 表示第i天不持有股票且處于冷凍期所得最多現金
定義了這三個狀態之后, 根據之前的經驗, 狀態轉移方程也不難寫出, 如下:
這里的have[i]沒有變化, cold[i]也很容易寫出, 唯一變化較大的就是no[i]了, 可能有人會感覺當天賣出股票也是滿足的, 因為到第二天才會是冷凍期.
官方題解的解釋是f[i]表示第 i 天結束之后的「累計最大收益」, 這種定義方式確實解決了這個問題, 但理解起來有點麻煩, 感覺繞了一下, 而且這種定義方式和之前的股票問題就有了差距, 不方便將它們整合起來, 所以我的理解是 只要賣出了股票就處于冷凍期, 不一定非要等到第二天, 這樣來理解, 問題就容易想清楚了.
原始碼
Python:
## 兩個狀態
## 未進行空間優化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1 :
return 0
have = [0] * n
no = [0] * n
have[0] = - prices[0]
no[0] = 0
have[1] = max(have[0], -prices[1])
no[1] = max(no[0], have[0] + prices[1])
for i in range(2, n) :
no[i] = max(no[i - 1], have[i - 1] + prices[i])
have[i] = max(have[i - 1], no[i - 2] - prices[i])
return no[n - 1]
## 空間優化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1 :
return 0
have = - prices[0] # 對have[0]初始化
no = 0
temp = no # 當i=2時, 記錄下第一個no[i-2]
have = max(have, -prices[1]) # 對have[1]初始化
no = max(no, have + prices[1])
for i in range(2, n) :
no_i2 = temp # 記錄下no[i-2]
temp = no # 記錄下no[i-1]
no = max(no, have + prices[i])
have = max(have, no_i2 - prices[i])
return no
## 三個狀態
## 未進行空間優化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if len == 0:
return 0
have = [0] * length # 表示第i天持有股票所得最多現金
no = [0] * length # 表示第i天不持有股票且不在冷凍期所得最多現金
cold = [0] * length # 表示第i天不持有股票且在冷凍期所得最多現金
have[0] = -prices[0] # 此時的持有股票就一定是買入股票了
no[0] = 0 # 不持有股票那么現金就是0
cold[0] = 0
for i in range(1, length):
have[i] = max(have[i-1], no[i-1] - prices[i]);
no[i] = max(no[i-1], cold[i-1]);
cold[i] = have[i-1] + prices[i];
return max(cold[-1], no[-1])
## 空間優化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if len == 0:
return 0
have = -prices[0] # 此時的持有股票就一定是買入股票了
no = 0 # 不持有股票那么現金就是0
cold = 0
for i in range(1, length):
have = max(have, no - prices[i]);
no = max(no, cold);
cold = have + prices[i];
return max(cold, no)
java:
// 兩個狀態
// 未進行空間優化
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n <= 1) {
return 0;
}
int[] have = new int[n];
int[] no = new int[n];
have[0] = - prices[0];
no[0] = 0;
have[1] = Math.max(have[0], -prices[1]);
no[1] = Math.max(no[0], have[0] + prices[1]);
for (int i = 2; i < n; i++) {
no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
have[i] = Math.max(have[i - 1], no[i - 2] - prices[i]);
}
return no[n - 1];
}
}
// 三個狀態
// 未進行空間優化
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
int[] have = new int[len]; // 表示第i天持有股票所得最多現金
int[] no = new int[len]; // 表示第i天不持有股票且不在冷凍期所得最多現金
int[] cold = new int[len]; // 表示第i天不持有股票且在冷凍期所得最多現金
have[0] = -prices[0]; // 此時的持有股票就一定是買入股票了
no[0] = 0; // 不持有股票那么現金就是0
cold[0] = 0;
for (int i = 1; i < len; i++) {
have[i] = Math.max(have[i-1], no[i-1] - prices[i]);
no[i] = Math.max(no[i-1], cold[i-1]);
cold[i] = have[i-1] + prices[i];
}
return Math.max(cold[len - 1], no[len - 1]);
}
}
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 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/houduan/335560.html
標籤：python