?📝個人主頁：@Sherry的成長之路
🏠學習社區(qū)：Sherry的成長之路（個人社區(qū)）
📖專欄鏈接：練題
🎯長路漫漫浩浩，萬事皆有期待

今天這期依舊是買賣股票的專題，兩道題難度都是困難，建議先看上一期的文章，搞懂買賣股票的最佳時機I和II再來看本章，可能會更加容易理解題解。

買賣股票的最佳時機 III

123. 買賣股票的最佳時機 III - 力扣（LeetCode）

買賣股票的最佳時機III實際上是I和II的拼湊版本。只能買賣最多兩次的含義是，可以買賣一次或者兩次，并不是說一定要買賣兩次，我們最后取得的答案是買賣一次和買賣兩次的最大利潤，但其實最終利潤如果是買賣一次大，那么買賣第二次時候利潤最終會與第一次是相等的數(shù)值，這個放在后面說。

dp數(shù)組的含義，以及遍歷順序與之前的那期兩道題是一樣的，只是dp數(shù)組的含義得到了擴展，0代表第一次買1代表第一次賣，2代表第二次買，3代表第二次賣，僅此而已。

遞推公式：遞推公式一共有四個，代表了買賣的第一次和第二次。為什么說它是上一期兩道題的結合版本，是因為買賣的第一次我們用到的是I的遞推公式，而買賣第二次就是用的II的遞推公式！買賣同樣的是代表了狀態(tài)，而不是當天一定買如股票賣出股票，它也可以是以前買入的。簡單的再說一次，第一次買股票的遞推公式是前一天的擁有的錢和在今天如果買了股票擁有的錢做對比，哪個大取哪個，第一次賣是前一天賣出后的擁有的錢，和如果前一天已經(jīng)持有股票的話，今天賣了會擁有的利潤，取最大值。第二次買賣也是一樣不多說了。直接給出四個遞推公式。

dp[i][0]=max(dp[i-1][0],-prices[i]);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數(shù)組的初始化：直接看初始化我們可以知道，第一次買賣再第一天我們都已經(jīng)分析過了買應該是-prices【i】，因為我們是假設的剛開始手上沒有錢初始值是0，不懂得看上一期的文章，賣獲得的是0，同一天買賣不賺錢。那第二次買賣我們該如何初始化？我們不妨假設給的數(shù)組只有一個數(shù)據(jù)，也就是只能在第一天買賣，要是這樣的想的話，我們第一次賣了之后手里錢和第一次買股票時候錢是一樣的，都是0，那么第二次買股票也初始化為-prices【i】，第二次賣也是0。

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

這就是這道題的代碼了，思路還是比較清晰的，代碼也不是十分復雜，但是要想到怎么解，沒有做過還是很難的。最后我們來說前面提到的，為什么如果第一次買賣的利潤大于第二次買賣，那么第二次買賣到最后也會變成第一次買賣的利潤數(shù)呢？其實這一點也很好解釋，和上一起的第二道題是一樣的，我們的從第一個遞推公式往后的每一個遞推公式都和上一個遞推公式有牽連，也就是說這些地推公式里的值，不僅依賴于自己本身的值，也依賴于上一個遞推公式所推算出來的最大利潤值。所以也就是說各個遞推公式一層影響著下一層，最后到了最后一個遞推公式，它所推出來的最大利潤就一定是兩次中的最大利潤。

買賣股票的最佳時機 IV

188. 買賣股票的最佳時機 IV - 力扣（LeetCode）

這道題算上是上一道題的進階版本，最多可以交易幾次，是由函數(shù)傳值影響，并不是直接固定的數(shù)值，那么我們還能像上一道題一樣手動列出有遞推公式嗎？其實我們可以借助于循環(huán)，幫助我們列出對應數(shù)量的遞推公式，一共可以買賣k次，那么一定得列出2*k個遞推公式，因為買賣是兩個公式。這道題與上一道不同的是，這道題我們需要列一個什么都不做的操作，來使遞推公式能夠模擬第一次買入的時候也可以像其他時候買入那樣具有泛型的規(guī)律。這樣說起來可能太抽象了，在后面讀者可以自行感悟。

dp數(shù)組含義：二維部分是需要2*k+1個這么大的空間。且含義與之前相同。

遞推公式：由于我們是借助循環(huán)來模擬列出各個遞推公式，而每一次買賣需要兩個遞推公式，那么很顯然我們只需列出兩個遞推公式讓它們循環(huán)k次就可以了。

兩個遞推公式分別是：

dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);

對上面兩個遞推公式做一個簡單的解釋，為什么是j+1，和j+2，而j又是什么呢？j其實是用來模擬第幾次買賣的變量，j從0開始走，我們已經(jīng)說過了，前面空出來一位不做操作，所以j+1模擬第一次買入，j+2模擬第一次賣出，這樣就使得第一次買股票也有規(guī)律可循，dp【i】【0】實際上就是為了占位的，它被初始化為0。方便了第一次的買入。j每次向后走兩位。

初始化：初始化和上面的一樣，也是買入初始化為-prices【i】，賣出初始化為0。只不過我們這里在創(chuàng)建數(shù)組時候，將各個位置初始為0之后，應該再用for循環(huán)把買入股票再初始化一次。關于這里為什么總要把買股票初始化為-prices【i】，不懂得也可以去看上一期文章，買股票最開始假設的是起初擁有現(xiàn)金0元，如果不初始化一下的話，就會導致一直為0，不買入股票。

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

以上就是本文章的全部內(nèi)容，兩道題都是困難難度的題，但是明白的思路會發(fā)現(xiàn)其實并沒有那么難。

總結：

今天我們完成了買賣股票的最佳時機 III、買賣股票的最佳時機 IV兩道題，相關的思想需要多復習回顧。接下來，我們繼續(xù)進行算法練習。希望我的文章和講解能對大家的學習提供一些幫助。

當然，本文仍有許多不足之處，歡迎各位小伙伴們隨時私信交流、批評指正！我們下期見~