目錄

題目鏈接：123.買賣股票的最佳時機III

思路

代碼

題目鏈接：188.買賣股票的最佳時機IV

思路

代碼

總結

---

題目鏈接：123.買賣股票的最佳時機III

思路

? ? ? ? 與之前買賣股票不同的是本題要求最多買賣兩次，那么dp數組以及遞推公式都有所改變。

? ? ? ? ①dp數組，dp[i][j]表示第i天剩余的最大金幣，j表示操作狀態：

????????????????0表示無操作

? ? ? ? ? ? ? ? 1表示第一次持有股票

? ? ? ? ? ? ? ? 2表示第一次不持有股票

? ? ? ? ? ? ? ? 3表示第二次持有股票

? ? ? ? ? ? ? ? 4表示第二次不持有股票

? ? ? ? ? ? ? ? 五種狀態都是依次連續的：

????????????????????????無操作->第一次持有->第一次不持有->第二次持有->第二次不持有

? ? ? ? ②遞推公式，要包含上述五種狀態的更新

? ? ? ? ? ? ? ? dp[i][0] = dp[i-1][0] 無操作與前一天保持一樣

? ? ? ? ? ? ? ? dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]) 可能之前就買過；如果沒買，說明之前都是無操作的狀態

? ? ? ? ? ? ? ? dp[i][2] = max(dp[i-1][2], dp[i-1][1] + price[i]) 可能之前就賣了；如果沒賣，說明第一次買的還在，今天賣

? ? ? ? ? ? ? ? dp[i][3] = max(dp[i-1][3], dp[i-1][2] - price[i]) 可能進行了一次買賣后，第二次買入了；如果沒買，說明已經進行了第一次的股票買賣，還沒進行第二次

? ? ? ? ? ? ? ? dp[i][4] = max(dp[i-1][4], dp[i-1][3] + price[i]) 可能將第二次買的股票賣了，或者今天賣

? ? ? ? ③dp數組初始化

? ? ? ? ? ? ? ? dp[0][0] = 0 無操作就是0

? ? ? ? ? ? ? ? dp[0][1] = -price[i] 第一天持有，表示第一天買入，減去當天股票價格

? ? ? ? ? ? ? ? dp[0][2] = 0 第一天不持有，表示沒有買入，還是0

? ? ? ? ? ? ? ? dp[0][3] = -price[i] 與第一次情況相同，可以認為第一天買了又賣了，現在是第二次

????????????????dp[0][4] = 0 第二次不持有，表示沒有買入，還是0

? ? ? ? ④遍歷順序，正序遍歷，因為所有的狀態更新都依賴于前一天

? ? ? ? ⑤推導dp數組

代碼

class Solution {
public:// dp數組第一維表示第i天，第二維表示狀態// 0表示無操作// 1表示第一次持有// 2表示第一次不持有// 3表示第二次持有// 4表示第二次不持有int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 1)return 0;vector<vector<int>> dp(len, vector<int>(5, 0));// dp數組初始化dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for (int i = 1; i < len; i++) {// 五種狀態的更新dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[len - 1][4];}
};

題目鏈接：188.買賣股票的最佳時機IV

思路

? ? ? ? 原理與123.買賣股票的最佳時機Ⅲ相同，可以買賣k次，創建dp數組時，第二維空間2k+1，初始化以及狀態更新時用for循環。

代碼

class Solution {
public:// dp數組第一維表示第i天// 第二維奇數表示第j次持有，偶數表示第j次不持有，0表示無操作int maxProfit(int k, vector<int>& prices) {int len = prices.size();if (len == 1)return 0;// 每次交易都包含持有和未持有兩種狀態，還有0表示無操作，所以共計2*k+1個狀態int s = 2 * k + 1;vector<vector<int>> dp(len, vector<int>(s, 0));// dp數組初始化，j從到2*kfor (int j = 0; j < s; j++) {if (j % 2 == 1) {dp[0][j] = -prices[0];} else {dp[0][j] = 0;}}// dp數組狀態更新for (int i = 1; i < len; i++) {dp[i][0] = dp[i - 1][0]; // 無操作單獨賦值for (int j = 1; j < s; j++) {// 奇數表示持有，偶數表示未持有// 每種狀態都由前一天推導而來，涉及前一天的當前狀態和前一種狀態if (j % 2 == 1) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);}}}return dp[len - 1][2 * k];}
};

總結

? ? ? ? ①買賣股票Ⅰ和Ⅱ分別是只能買賣一次和不限次數的買賣；買賣股票Ⅲ和Ⅳ分別是只能買賣兩次和買賣k次。相同點是當天的狀態只能由昨天推導而來，不同點是狀態的多少

? ? ? ? ②看了買賣股票Ⅲ的題解，AC后，單獨完成了買賣股票Ⅳ，規律性很強

? ? ? ? ③在做這類題時，最重要的是搞清楚dp數組的含義，并且要包含所有的狀態