📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

你可以點擊下方鏈接，進行不同專題的動態規劃的學習

點擊鏈接	開始學習
斐波那契數列模型	路徑問題
簡單多狀態（一）	簡單多狀態（二）
子數組系列（一）	子數組系列（二）
子序列問題（一）	子序列問題（二）
回文串問題	兩個數組dp問題（一）
兩個數組的dp問題（二）	01背包問題
完全背包	二維的背包問題
其他

---

309. 買賣股票的最佳時機含冷凍期

題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

優質解

思路：

• 本題的三狀態怎么來的，本來是買（已賣） / 賣，但是本題多了一個冷凍期，限制的是當天買的行為，所以變成了三狀態。已賣 + 可買 / 已賣 + 不可買 / 賣
• dp[i]：當天結束時，最大收益。當天結束后的狀態又可以再細分（開 3 * n的數組）。
  • 持股dp[0]
  • dp[1]不持股且明天不可以買
  • dp[2]不持股且明天可以買
• 狀態轉移方程（當天結束的狀態：由前一天狀態和當天行為決定）：
  • 可變成持股狀態的：
    • 前一天不持股且明天可以買 + 當天買入；
    • 前一天持股 + 當天不變
  • 可變成不持股且明天不可買的：
    • 前一天持股 + 當天賣出
  • 可變成不持股且明天可買的：
    • 前一天不持股且明天可買 + 當天不變；
    • 前一天不持股且明天不可買 + 當天不變
• 由上可推出方程
• dp[0][i] = max(dp[2][i - 1] - price[i], dp[0][i - 1])
• dp[1][i] = dp[0][i - 1] + price[i]
• dp[2][i] = max(dp[1][i - 1], dp[2][i - 1])
• 初始化：dp[0][0] = -price[0]，dp[1][0] = dp[2][0] = 0
• 填表順序：三個一起填
• 返回值：max(dp[1][n - 1], dp[2][n - 1])

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size(); vector<vector<int>> dp(3, vector(n, 0));dp[0][0] = -prices[0];for(int i = 1; i < n; i++){dp[0][i] = max(dp[2][i - 1] - prices[i], dp[0][i - 1]);dp[1][i] = dp[0][i - 1] + prices[i];dp[2][i] = max(dp[1][i - 1], dp[2][i - 1]);}return max(dp[1][n - 1], dp[2][n - 1]);}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

714. 買賣股票的最佳時機含手續費

題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

個人解

思路：

// dp[0][i] 第 i 天結束后為持股狀態時的最大收益
// dp[1][i] 第 i 天結束后為不持股狀態時的最大收益
// dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);
// dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);

不多說了，難度不如上一題
用時：10:00
屎山代碼：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(2, vector(n, 0));dp[0][0] = -prices[0] - fee; // 讓買入算手續費for(int i = 1; i < n; i++){dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);}return dp[1][n - 1];}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

123. 買賣股票的最佳時機 III

題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

優質解

思路：

• 通過分析狀態表示，我們發現必須要三維才能夠很好的表示狀態
• 第一維：持股 / 不持股，第二維：最大利潤 ，第三維：所剩交易次數

但是我們也可以把持股和不持股分出來：

• f[i][j] : "持股"狀態，第i天結束之后，完成了j次交易，的最大利潤
• g[i][j] : "不持股"狀態，第i天結束之后，完成了j次交易，的最大利潤

可見，下標直接表示交易次數
我們規定，只有在賣出的時候，交易次數才++
則狀態轉移方程：

• f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])
• g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])

初始化（其實是解決越界行為）：

• 初始時，交易次數為 1 和 2 的初始化
  • 我們可以讓f[0][1] = f[0][2] = - INT_MAX / 2，即：取最小值（比所有可能的結果都小），使得該位置不會被下一天max選到，從而不影響正常的狀態轉移（g同理）
  • /2的原因：因為g[i - 1][j] - prices[i]會導致負數溢出，所以控制一下
• f[i - 1][j - 1] + prices[i]的操作：j - 1會越界
  • 而這個式子中j等于0是無意義的，因為如果當天有賣出行為，則g[i][j]的j一定 >= 1
  • 因此，我們可以把式子變換成：

g[i][j] = g[i - 1][j];
if(j > 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);

• 是從第1天開始填的，基于第0天，所以：f[0][0] = -p[0]、g[0][0] = 0

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(3, -INT_MAX / 2));auto g = f;f[0][0] = -prices[0]; g[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j < 3; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j >= 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);}}return max(max(g[n - 1][0], g[n - 1][1]), g[n - 1][2]);}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

188. 買賣股票的最佳時機 IV

題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

個人解

思路：

• 和上一題一樣

用時：6:00
屎山代碼：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(k + 1, -INT_MAX/2));auto g = f;f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j >= 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);}}int ans = 0;for(int i = 0; i <= k; i++)ans = max(ans, g[n - 1][i]);return ans;}
};

時間復雜度：$O(n?k)$
空間復雜度：$O(n?k)$

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！