刷股票問題看到的一個大神解答之碗，搬運過來呛凶，給大家分享。
作者：labuladong
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)弹谁，非商業(yè)轉(zhuǎn)載請注明出處。
下面是正文：
很多讀者抱怨股票系列問題奇技淫巧太多句喜，如果面試真的遇到這類問題预愤，基本不會想到那些巧妙的辦法，怎么辦咳胃？所以本文拒絕奇技淫巧植康，而是穩(wěn)扎穩(wěn)打，只用一種通用方法解決所用問題展懈，以不變應萬變销睁。
這篇文章用狀態(tài)機的技巧來解決供璧，可以全部提交通過。不要覺得這個名詞高大上冻记，文學詞匯而已睡毒，實際上就是 DP table，看一眼就明白了冗栗。
先隨便抽出一道題演顾，看看別人的解法：
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
int s1=-prices[0],s2=INT_MIN,s3=INT_MIN,s4=INT_MIN;
for(int i=1;i<prices.size();++i) {
s1 = max(s1, -prices[i]);
s2 = max(s2, s1+prices[i]);
s3 = max(s3, s2-prices[i]);
s4 = max(s4, s3+prices[i]);
}
return max(0,s4);
}
能看懂吧？會做了嗎隅居？不可能的钠至，你看不懂，這才正常胎源。就算你勉強看懂了棉钧，下一個問題你還是做不出來。為什么別人能寫出這么詭異卻又高效的解法呢乒融？因為這類問題是有框架的掰盘，但是人家不會告訴你的，因為一旦告訴你赞季，你五分鐘就學會了愧捕，該算法題就不再神秘，變得不堪一擊了申钩。
本文就來告訴你這個框架次绘，然后帶著你一道一道秒殺。
這 6 道股票買賣問題是有共性的撒遣，我們通過對第四題（限制最大交易次數(shù)為 k）的分析一道一道解決邮偎。因為第四題是一個最泛化的形式，其他的問題都是這個形式的簡化义黎。
第一題是只進行一次交易禾进，相當于 k = 1；第二題是不限交易次數(shù)廉涕，相當于 k = +infinity（正無窮）泻云；第三題是只進行 2 次交易，相當于 k = 2狐蜕；剩下兩道也是不限次數(shù)宠纯，但是加了交易「冷凍期」和「手續(xù)費」的額外條件，其實就是第二題的變種层释，都很容易處理婆瓜。
一、窮舉框架
首先贡羔，還是一樣的思路：如何窮舉廉白？這里的窮舉思路和上篇文章遞歸的思想不太一樣个初。
遞歸其實是符合我們思考的邏輯的，一步步推進蒙秒，遇到無法解決的就丟給遞歸勃黍，一不小心就做出來了，可讀性還很好晕讲。缺點就是一旦出錯，你也不容易找到錯誤出現(xiàn)的原因马澈。比如上篇文章的遞歸解法瓢省，肯定還有計算冗余，但確實不容易找到痊班。
而這里勤婚，我們不用遞歸思想進行窮舉，而是利用「狀態(tài)」進行窮舉涤伐。我們具體到每一天馒胆，看看總共有幾種可能的「狀態(tài)」，再找出每個「狀態(tài)」對應的「選擇」凝果。我們要窮舉所有「狀態(tài)」祝迂，窮舉的目的是根據(jù)對應的「選擇」更新狀態(tài)。聽起來抽象器净，你只要記住「狀態(tài)」和「選擇」兩個詞就行型雳，下面實操一下就很容易明白了。
for 狀態(tài)1 in 狀態(tài)1的所有取值：
for 狀態(tài)2 in 狀態(tài)2的所有取值：
for ...
dp[狀態(tài)1][狀態(tài)2][...] = 擇優(yōu)(選擇1山害，選擇2...)
比如說這個問題纠俭，每天都有三種「選擇」：買入、賣出浪慌、無操作冤荆，我們用 buy, sell, rest 表示這三種選擇。但問題是权纤，并不是每天都可以任意選擇這三種選擇的钓简，因為 sell 必須在 buy 之后，buy 必須在 sell 之后妖碉。那么 rest 操作還應該分兩種狀態(tài)涌庭，一種是 buy 之后的 rest（持有了股票），一種是 sell 之后的 rest（沒有持有股票）欧宜。而且別忘了坐榆，我們還有交易次數(shù) k 的限制，就是說你 buy 還只能在 k > 0 的前提下操作冗茸。
很復雜對吧席镀，不要怕匹中，我們現(xiàn)在的目的只是窮舉，你有再多的狀態(tài)豪诲，老夫要做的就是一把梭全部列舉出來顶捷。這個問題的「狀態(tài)」有三個，第一個是天數(shù)屎篱，第二個是允許交易的最大次數(shù)服赎，第三個是當前的持有狀態(tài)（即之前說的 rest 的狀態(tài)，我們不妨用 1 表示持有交播，0 表示沒有持有）重虑。然后我們用一個三維數(shù)組就可以裝下這幾種狀態(tài)的全部組合：
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 為天數(shù)，大 K 為最多交易數(shù)
此問題共 n × K × 2 種狀態(tài)秦士，全部窮舉就能搞定缺厉。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
而且我們可以用自然語言描述出每一個狀態(tài)的含義，比如說 dp[3][2][1] 的含義就是：今天是第三天隧土，我現(xiàn)在手上持有著股票提针，至今最多進行 2 次交易。再比如 dp[2][3][0] 的含義：今天是第二天曹傀，我現(xiàn)在手上沒有持有股票辐脖，至今最多進行 3 次交易。很容易理解卖毁，對吧揖曾？
我們想求的最終答案是 dp[n - 1][K][0]，即最后一天亥啦，最多允許 K 次交易炭剪，最多獲得多少利潤。讀者可能問為什么不是 dp[n - 1][K][1]翔脱？因為 [1] 代表手上還持有股票奴拦，[0] 表示手上的股票已經(jīng)賣出去了，很顯然后者得到的利潤一定大于前者届吁。
記住如何解釋「狀態(tài)」错妖，一旦你覺得哪里不好理解，把它翻譯成自然語言就容易理解了疚沐。
二暂氯、狀態(tài)轉(zhuǎn)移框架
現(xiàn)在，我們完成了「狀態(tài)」的窮舉亮蛔，我們開始思考每種「狀態(tài)」有哪些「選擇」痴施，應該如何更新「狀態(tài)」。只看「持有狀態(tài)」，可以畫個狀態(tài)轉(zhuǎn)移圖辣吃。
通過這個圖可以很清楚地看到动遭，每種狀態(tài)（0 和 1）是如何轉(zhuǎn)移而來的。根據(jù)這個圖神得，我們來寫一下狀態(tài)轉(zhuǎn)移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 選擇 rest , 選擇 sell )
解釋：今天我沒有持有股票厘惦，有兩種可能：
要么是我昨天就沒有持有，然后今天選擇 rest哩簿，所以我今天還是沒有持有宵蕉；
要么是我昨天持有股票，但是今天我 sell 了节榜，所以我今天沒有持有股票了国裳。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 選擇 rest , 選擇 buy )
解釋：今天我持有著股票，有兩種可能：
要么我昨天就持有著股票全跨，然后今天選擇 rest，所以我今天還持有著股票亿遂；
要么我昨天本沒有持有浓若，但今天我選擇 buy，所以今天我就持有股票了蛇数。
這個解釋應該很清楚了挪钓，如果 buy，就要從利潤中減去 prices[i]耳舅，如果 sell碌上，就要給利潤增加 prices[i]。今天的最大利潤就是這兩種可能選擇中較大的那個浦徊。而且注意 k 的限制馏予，我們在選擇 buy 的時候，把 k 減小了 1盔性，很好理解吧霞丧，當然你也可以在 sell 的時候減 1，一樣的冕香。
現(xiàn)在蛹尝，我們已經(jīng)完成了動態(tài)規(guī)劃中最困難的一步：狀態(tài)轉(zhuǎn)移方程。如果之前的內(nèi)容你都可以理解悉尾，那么你已經(jīng)可以秒殺所有問題了突那，只要套這個框架就行了。不過還差最后一點點构眯，就是定義 base case愕难，即最簡單的情況。
dp[-1][k][0] = 0
解釋：因為 i 是從 0 開始的，所以 i = -1 意味著還沒有開始务漩，這時候的利潤當然是 0 拄衰。
dp[-1][k][1] = -infinity
解釋：還沒開始的時候，是不可能持有股票的饵骨，用負無窮表示這種不可能翘悉。
dp[i][0][0] = 0
解釋：因為 k 是從 1 開始的，所以 k = 0 意味著根本不允許交易居触，這時候利潤當然是 0 妖混。
dp[i][0][1] = -infinity
解釋：不允許交易的情況下，是不可能持有股票的轮洋，用負無窮表示這種不可能制市。
把上面的狀態(tài)轉(zhuǎn)移方程總結(jié)一下：
base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
狀態(tài)轉(zhuǎn)移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
讀者可能會問，這個數(shù)組索引是 -1 怎么編程表示出來呢弊予，負無窮怎么表示呢祥楣？這都是細節(jié)問題，有很多方法實現(xiàn)『浩猓現(xiàn)在完整的框架已經(jīng)完成误褪，下面開始具體化。
三碾褂、秒殺題目
第一題兽间，k = 1
直接套狀態(tài)轉(zhuǎn)移方程，根據(jù) base case正塌，可以做一些化簡：
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
= max(dp[i-1][1][1], -prices[i])
解釋：k = 0 的 base case嘀略，所以 dp[i-1][0][0] = 0。
現(xiàn)在發(fā)現(xiàn) k 都是 1乓诽，不會改變帜羊，即 k 對狀態(tài)轉(zhuǎn)移已經(jīng)沒有影響了。
可以進行進一步化簡去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
直接寫出代碼：
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
顯然 i = 0 時 dp[i-1] 是不合法的问裕。這是因為我們沒有對 i 的 base case 進行處理逮壁。可以這樣處理：
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
dp[i][0] = 0;
// 解釋：
// dp[i][0]
// = max(dp[-1][0], dp[-1][1] + prices[i])
// = max(0, -infinity + prices[i]) = 0
dp[i][1] = -prices[i];
//解釋：
// dp[i][1]
// = max(dp[-1][1], dp[-1][0] - prices[i])
// = max(-infinity, 0 - prices[i])
// = -prices[i]
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
第一題就解決了粮宛，但是這樣處理 base case 很麻煩窥淆，而且注意一下狀態(tài)轉(zhuǎn)移方程，新狀態(tài)只和相鄰的一個狀態(tài)有關巍杈，其實不用整個 dp 數(shù)組忧饭，只需要一個變量儲存相鄰的那個狀態(tài)就足夠了，這樣可以把空間復雜度降到 O(1):
// k == 1
int maxProfit_k_1(int[] prices) {
int n = prices.length;
// base case: dp[-1][0] = 0, dp[-1][1] = -infinity
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
// dp[i][1] = max(dp[i-1][1], -prices[i])
dp_i_1 = Math.max(dp_i_1, -prices[i]);
}
return dp_i_0;
}
兩種方式都是一樣的筷畦，不過這種編程方法簡潔很多词裤。但是如果沒有前面狀態(tài)轉(zhuǎn)移方程的引導刺洒，是肯定看不懂的。后續(xù)的題目吼砂，我主要寫這種空間復雜度 O(1) 的解法逆航。
第二題，k = +infinity
如果 k 為正無窮渔肩，那么就可以認為 k 和 k - 1 是一樣的因俐。可以這樣改寫框架：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
= max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
我們發(fā)現(xiàn)數(shù)組中的 k 已經(jīng)不會改變了周偎，也就是說不需要記錄 k 這個狀態(tài)了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
直接翻譯成代碼：
int maxProfit_k_inf(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}
第三題抹剩，k = +infinity with cooldown
每次 sell 之后要等一天才能繼續(xù)交易。只要把這個特點融入上一題的狀態(tài)轉(zhuǎn)移方程即可：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解釋：第 i 天選擇 buy 的時候蓉坎，要從 i-2 的狀態(tài)轉(zhuǎn)移澳眷，而不是 i-1 。
翻譯成代碼：
int maxProfit_with_cool(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
int dp_pre_0 = 0; // 代表 dp[i-2][0]
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
第四題蛉艾，k = +infinity with fee
每次交易要支付手續(xù)費钳踊，只要把手續(xù)費從利潤中減去即可。改寫方程：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解釋：相當于買入股票的價格升高了勿侯。
在第一個式子里減也是一樣的箍土，相當于賣出股票的價格減小了。
直接翻譯成代碼：
int maxProfit_with_fee(int[] prices, int fee) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
}
return dp_i_0;
}
第五題罐监，k = 2
k = 2 和前面題目的情況稍微不同，因為上面的情況都和 k 的關系不太大瞒爬。要么 k 是正無窮弓柱，狀態(tài)轉(zhuǎn)移和 k 沒關系了；要么 k = 1侧但，跟 k = 0 這個 base case 挨得近矢空，最后也沒有存在感。
這道題 k = 2 和后面要講的 k 是任意正整數(shù)的情況中禀横，對 k 的處理就凸顯出來了屁药。我們直接寫代碼，邊寫邊分析原因柏锄。
原始的動態(tài)轉(zhuǎn)移方程酿箭，沒有可化簡的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
按照之前的代碼，我們可能想當然這樣寫代碼（錯誤的）：
int k = 2;
int[][][] dp = new int[n][k + 1][2];
for (int i = 0; i < n; i++)
if (i - 1 == -1) { /* 處理一下 base case*/ }
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
return dp[n - 1][k][0];
為什么錯誤趾娃？我這不是照著狀態(tài)轉(zhuǎn)移方程寫的嗎缭嫡？
還記得前面總結(jié)的「窮舉框架」嗎？就是說我們必須窮舉所有狀態(tài)抬闷。其實我們之前的解法妇蛀，都在窮舉所有狀態(tài)耕突，只是之前的題目中 k 都被化簡掉了。這道題由于沒有消掉 k 的影響评架，所以必須要對 k 進行窮舉：
int max_k = 2;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++) {
for (int k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
/* 處理 base case */
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
// 窮舉了 n × max_k × 2 個狀態(tài)眷茁，正確。
return dp[n - 1][max_k][0];
如果你不理解纵诞，可以返回第一點「窮舉框架」重新閱讀體會一下上祈。
這里 k 取值范圍比較小，所以可以不用 for 循環(huán)挣磨，直接把 k = 1 和 2 的情況手動列舉出來也可以：
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
int maxProfit_k_2(int[] prices) {
int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
for (int price : prices) {
dp_i20 = Math.max(dp_i20, dp_i21 + price);
dp_i21 = Math.max(dp_i21, dp_i10 - price);
dp_i10 = Math.max(dp_i10, dp_i11 + price);
dp_i11 = Math.max(dp_i11, -price);
}
return dp_i20;
}
有狀態(tài)轉(zhuǎn)移方程和含義明確的變量名指導雇逞，相信你很容易看懂。其實我們可以故弄玄虛茁裙，把上述四個變量換成 a, b, c, d塘砸。這樣當別人看到你的代碼時就會一頭霧水，大驚失色晤锥，不得不對你肅然起敬掉蔬。
第六題，k = any integer
有了上一題 k = 2 的鋪墊矾瘾，這題應該和上一題的第一個解法沒啥區(qū)別女轿。但是出現(xiàn)了一個超內(nèi)存的錯誤，原來是傳入的 k 值會非常大壕翩，dp 數(shù)組太大了◎燃＃現(xiàn)在想想，交易次數(shù) k 最多有多大呢放妈？
一次交易由買入和賣出構(gòu)成北救，至少需要兩天。所以說有效的限制 k 應該不超過 n/2芜抒，如果超過珍策，就沒有約束作用了，相當于 k = +infinity宅倒。這種情況是之前解決過的攘宙。
直接把之前的代碼重用：
int maxProfit_k_any(int max_k, int[] prices) {
int n = prices.length;
if (max_k > n / 2)
return maxProfit_k_inf(prices);
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++)
for (int k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
/* 處理 base case */
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
return dp[n - 1][max_k][0];
}
至此，6 道題目通過一個狀態(tài)轉(zhuǎn)移方程全部解決拐迁。
四蹭劈、最后總結(jié)
本文給大家講了如何通過狀態(tài)轉(zhuǎn)移的方法解決復雜的問題，用一個狀態(tài)轉(zhuǎn)移方程秒殺了 6 道股票買賣問題线召，現(xiàn)在想想链方，其實也不算難對吧？這已經(jīng)屬于動態(tài)規(guī)劃問題中較困難的了灶搜。
關鍵就在于列舉出所有可能的「狀態(tài)」祟蚀，然后想想怎么窮舉更新這些「狀態(tài)」工窍。一般用一個多維 dp 數(shù)組儲存這些狀態(tài)，從 base case 開始向后推進前酿，推進到最后的狀態(tài)患雏，就是我們想要的答案。想想這個過程罢维，你是不是有點理解「動態(tài)規(guī)劃」這個名詞的意義了呢淹仑？
具體到股票買賣問題，我們發(fā)現(xiàn)了三個狀態(tài)肺孵，使用了一個三維數(shù)組匀借，無非還是窮舉 + 更新，不過我們可以說的高大上一點平窘，這叫「三維 DP」吓肋，怕不怕？這個大實話一說瑰艘，立刻顯得你高人一等是鬼，名利雙收有沒有。
所以，大家不要被各種高大上的名詞嚇到，再多的困難問題盏浇，奇技淫巧，也不過是基本套路的不斷升級組合產(chǎn)生的攒发。只要把住算法的底層原理，即可舉一反三，逐個擊破。
